😂二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
if(!nums1.size() || !nums2.size())
return vector<int>();
vector<int> res;
int lo, ho, mid;
sort(nums2.begin(), nums2.end());
for(auto x: nums1) {
lo = 0;
ho = nums2.size() - 1;
while(lo < ho) {
mid = lo + (ho - lo) / 2;
if(nums2[mid] < x) {
lo = mid + 1;
} else {
ho = mid;
}
}
if(nums2[lo] == x) {
res.push_back(x);
nums2.erase(nums2.begin() + lo);
if(!nums2.size())
return res;
}
}
return res;
}
};
|
Accepted
61/61 cases passed (12 ms)
Your runtime beats 55.05 % of cpp submissions
Your memory usage beats 52.41 % of cpp submissions (9.4 MB)
😧map
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int ,int> mp;
for(auto x : nums1) {
if(mp.count(x)) {
mp[x] += 1;
} else
mp[x] = 1;
}
vector<int> vec;
for(auto x : nums2) {
if(mp.count(x)) {
if(mp[x] > 0) {
mp[x]--;
vec.push_back(x);
}
if(mp[x] == 0) {
mp.erase(x);
}
}
}
return vec;
}
};
|
Accepted
61/61 cases passed (12 ms)
Your runtime beats 46.09 % of cpp submissions
Your memory usage beats 16.76 % of cpp submissions (9.7 MB)
