SHARE
TWEET

Untitled

bbescos Jan 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. // Run-time complexity O(n*m)
  10. // Memory complexity O(n)
  11. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  12.    
  13.     // Get size of vector nums1
  14.     int n = nums1.size();
  15.    
  16.     // Declare result variable
  17.     vector<int> result;
  18.            
  19.     for (int num1 : nums1) {
  20.         // Iterate over numbers in nums1
  21.         int times = count(nums2.begin(), nums2.end(), num1); //O(m)
  22.         // Count how many of that number there are in nums2
  23.         if (times > 0) {
  24.             // if at least 1, push it
  25.             result.push_back(num1);
  26.            
  27.             // erase 1
  28.             vector<int>::iterator it = find(nums2.begin(), nums2.end(), num1);
  29.             nums2.erase(it);
  30.         }
  31.        // loop
  32.     }
  33.    
  34.     return result;
  35. }
  36.    
  37. // Run-time complexity O(max(nlogn, mlogm))
  38. // Memory complexity O(n)
  39. vector<int> intersect_2(vector<int>& nums1, vector<int>& nums2) {
  40.        
  41.     vector<int> result;
  42.        
  43.     if (nums1.empty() || nums2.empty())
  44.         return result;
  45.        
  46.     int i = 0;
  47.     int j = 0;
  48.        
  49.     sort(nums1.begin(), nums1.end()); //O(nlogn)
  50.     sort(nums2.begin(), nums2.end()); //O(mlogm)
  51.        
  52.     while (i < nums1.size() && j < nums2.size()) {
  53.         if (nums1[i] < nums2[j])
  54.             ++i;
  55.         else{
  56.             if (nums1[i] > nums2[j])
  57.                 ++j;
  58.             else {
  59.                 result.push_back(nums1[i]);
  60.                 ++i;
  61.                 ++j;
  62.             }
  63.         }
  64.            
  65.     }
  66.  
  67.     return result;
  68. }
  69.  
  70. // Run-time complexity O(max(n, m))
  71. // Memory complexity O(n)
  72. vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
  73.     unordered_map<int, int> hashmap;
  74.     vector<int> result;
  75.  
  76.     if (nums1.empty() || nums2.empty())
  77.         return result;
  78.  
  79.     for (int num : nums1) {
  80.         ++hashmap[num];
  81.     }
  82.  
  83.     for (int num : nums2) {
  84.         if (hashmap[num] != 0) {
  85.             result.push_back(num);
  86.             --hashmap[num];
  87.         }
  88.     }
  89.  
  90.     return result;
  91. }
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