SHARE
TWEET

Untitled

bbescos Jan 23rd, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Run-time complexity O(n*m)
  2. // Memory complexity O(1) o O(n)?? Porque como me estoy generando result...
  3. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  4.        
  5.     int n = nums1.size();
  6.     vector<int> result;
  7.        
  8.     for (int i = 0; i < n; ++i) {
  9.         int times = count(nums2.begin(), nums2.end(), nums1[i]); //O(m)
  10.         if (times > 0) {
  11.             result.push_back(nums1[i]);
  12.             vector<int>::iterator it = find(nums2.begin(), nums2.end(), nums1[i]);
  13.             nums2.erase(it);
  14.         }
  15.     }
  16.  
  17.     return result;
  18. }
  19.    
  20. // Run-time complexity O(max(nlogn, mlogm))
  21. // Memory complexity O(1) o O(n)?? Porque como me estoy generando result...
  22. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  23.        
  24.     vector<int> result;
  25.        
  26.     if (nums1.empty() || nums2.empty())
  27.         return result;
  28.        
  29.     int i = 0;
  30.     int j = 0;
  31.        
  32.     sort(nums1.begin(), nums1.end()); //O(nlogn)
  33.     sort(nums2.begin(), nums2.end()); //O(mlogm)
  34.        
  35.     while (i < nums1.size() && j < nums2.size()) {
  36.         if (nums1[i] < nums2[j])
  37.             ++i;
  38.         else{
  39.             if (nums1[i] > nums2[j])
  40.                 ++j;
  41.             else {
  42.                 result.push_back(nums1[i]);
  43.                 ++i;
  44.                 ++j;
  45.             }
  46.         }
  47.            
  48.     }
  49.  
  50.     return result;
  51.     }
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