0%

[Leetcode]349. Intersection of Two Arrays(C++)

题目描述

题目链接:349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

例子

例子 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

例子 2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints

  • 1 <= nums1.length, nums2.length <= 100`
  • 0 <= nums1[i], nums2[i] <= 1000

解题思路

首先将两个数组排序,然后使用其中一个数组的元素在另一个数组进行二分查找即可,注意排除重复项。代码如下:

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
30
31
32
33
34
35
36
37
38
39
#include <algorithm>
#include <vector>

class Solution {
public:
std::vector<int> intersection(std::vector<int>& nums1,
std::vector<int>& nums2) {
std::sort(nums1.begin(), nums1.end());
std::sort(nums2.begin(), nums2.end());

std::vector<int> intersection;
for (size_t i = 0; i < nums1.size(); ++i) {
if (i > 0 && nums1[i] == nums1[i - 1]) continue;
if (binary_search(nums2, nums1[i])) {
intersection.push_back(nums1[i]);
}
}

return intersection;
}

private:
bool binary_search(const std::vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}

return false;
}
};
  • 时间复杂度: O(log n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 349.IntersectionOfTwoArrays.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions