# 题目描述 LeetCode 349

Given two arrays, write a function to compute their intersection

Example:
Given nums1 = `[1, 2, 2, 1]`, nums2 = `[2, 2]`, return `[2]`

Note:

• Each element in the result must be unique
• The result can be in any order

• 找到两个数组的交集并返回

# 解题思路

• 1，首先用冒泡排序将两个数组分别按照递增排序
• 2，取出数组1中的每一个数字，用二分查找方法去数组2中查找，如果找到则返回1，否则返回0
• 3，如果找到则将查找的这个数字放到待返回的数组中

# Code

``````# include

// 冒泡排序
void Bubble(int *tt, int size){
int i, j ;
int temp;

for (i = 0; i < size - 1; i ++){
for (j = i + 1; j < size; j ++){
if(tt[i] > tt[j])
{
temp = tt[i];
tt[i] = tt[j];
tt[j] = temp;
}
}
}
}

// 二分查找
int BinarySearch(int rr[], int left, int right, int x){
int index = (right + left) / 2;
int mid = rr[index];

if(left <= right){
if(x < mid){
return BinarySearch(rr, 0, index - 1, x);
}
else if(x > mid){

return BinarySearch(rr, index + 1, right, x);
}
else{
return 1;
}
}
else{
return 0;
}
}

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int i;
static int temp[10000];

Bubble(nums1, nums1Size);
Bubble(nums2, nums2Size);
for(i = 0; i < nums1Size; i ++){
if (i == 0){
if(BinarySearch(nums2, 0, nums2Size - 1, nums1[i]) == 1){
temp[(*returnSize) ++] = nums1[i];
}
}
else{
if(nums1[i] != nums1[i - 1]){
if(BinarySearch(nums2, 0, nums2Size - 1, nums1[i]) == 1){
temp[(*returnSize) ++] = nums1[i];
}
}
}
}
return temp;
}

int main()
{
int a[10] = {1, 2, 2, 1};
int b[10] = {1, 1};
int returnSize = 0;
int i;
int* temp;

temp = intersection(a, 4, b, 2, &returnSize);
for(i = 0; i < returnSize; i ++){
printf("%d  ", temp[i]);
}
}
``````
• 思路二，和思路一一样，C++实现
``````class Solution {
public:
vector intersection(vector& nums1, vector& nums2) {
vector result;

if(nums1.size() == 0 || nums2.size() == 0){
return result;
}

// 对数组排序, 满足二分查找的前提条件
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());

// 对 nums1 去重
int length1 = removeDuplicates(nums1);
int length2 = removeDuplicates(nums2);

for(int i=0; i < length1; i++){
if(BinarySearch(nums2, 0, length2-1, nums1[i])){
result.push_back(nums1[i]);
}
}
return result;
}

int removeDuplicates(vector& num){
int length = 1;
for(int i=1; i < num.size(); i++){
if(num[i] != num[i-1]){
num[length++] = num[i];
}
}
return length;
}

bool BinarySearch(vector& num, int left, int right, int target){
if(left <= right){
int indexOfmed = (left + right) / 2;
int med = num[indexOfmed];

if(target < med){
return BinarySearch(num, left, indexOfmed-1, target);
}
else if(target > med){
return BinarySearch(num, indexOfmed+1, right, target);
}
else{
return true;
}
}
else{
return false;
}
}
};
``````
• 思路三 STL中set方法
``````class Solution {
public:
vector intersection(vector& nums1, vector& nums2) {
set temp;
vector result;

// 如果有一个数组甚至两个数组输入为空，则返回交集为空
if(nums1.size() == 0 || nums2.size() == 0){
return result;
}

// 将数组nums1加入set集合中，注意此处加入的过程中自动去掉重复值
for(int i=0; i < nums1.size(); i++){
temp.insert(nums1[i]);
}

for(int i=0; i < nums2.size(); i++){
// 如果在set中能找到nums2[i]，则erase返回值为1，否则返回0
if(temp.erase(nums2[i])){
result.push_back(nums2[i]);
}
}
return result;
}
};
``````

# 反思

• runtime 这么长的原因，应该是递归的使用，递归很耗费时间的！！！