• API
• FAQ
• Tools
• Archive
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.

Top