SHARE
TWEET

Untitled

bbescos Jan 25th, 2019 54 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     // Memory Complexity O(1)
  5.     // Run-time Complexity O(n2)
  6.     /*int removeDuplicates(vector<int>& nums) {
  7.        
  8.         if (nums.empty()) {
  9.             return nums.size();
  10.         }
  11.        
  12.         int i = 0;
  13.         while (i < nums.size() - 1) {
  14.  
  15.             if (nums[i] == nums[i + 1])
  16.                 nums.erase(nums.begin() + i); //O(n)
  17.             else
  18.                 ++i;
  19.         }
  20.        
  21.         return nums.size();
  22.     }*/
  23.    
  24.     // i = 0; it = 0; j = 1
  25.     // 0 1 1 1 2 2 3
  26.     // i = 1; it = 1; j = 2
  27.     // 0 1 1 1 2 2 3
  28.     // i = 4; it = 2; j = 5
  29.     // 0 1 2 1 2 2 3
  30.     // i = 5; it = 3; j = 6
  31.     // 0 1 2 3 2 2 3
  32.     // Memory Complexity O(n2)
  33.     // Run-time Complexity O(1)
  34.     int removeDuplicates(vector<int>& nums) {
  35.        
  36.         int it = 0;
  37.         int i = 0;
  38.         while(i<nums.size())
  39.         {
  40.             int j = i + 1;
  41.             while(nums[i] == nums[j])
  42.                 ++j;
  43.            
  44.             nums[it++] = nums[i];
  45.             i = j;          
  46.         }
  47.        
  48.         return it;
  49.     }
  50. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top