题目描述
题目链接:349. Intersection of Two Arrays
Given two integer arrays
nums1
andnums2
, 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 <= 10
0`0 <= nums1[i], nums2[i] <= 1000
解题思路
首先将两个数组排序,然后使用其中一个数组的元素在另一个数组进行二分查找即可,注意排除重复项。代码如下:
#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