题目描述 LeetCode 350

Given two arrays, write a function to compute their intersection.

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

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

题目解读

• 找出两个数字的交集，并返回，交集可重复(参考Example)

解题思路

Code

• 思路一 ， 给数组2定义一个标识数组 b[ ]，如果已找到则标记该位为1，每次从数组1中取出的数字只能在数组2的标识为0的索引位下查找

# include<stdio.h>

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

    for(i = 0; i < nums2Size; i ++){
        b[i] = 0;
    }

    for(i = 0; i < nums1Size; i ++){
        for (j = 0; j < nums2Size; j ++){
            if(b[j] == 0){
                if(nums1[i] == nums2[j]){
                    b[j] = 1;
                    temp[(*returnSize) ++] = nums1[i];
                    break;
                }
            }
        } 
    } 

    return temp;
}

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

    temp = intersection(a, 4, b, 2, &returnSize);
    for(i = 0; i < returnSize; i ++){
        printf("%d  ", temp[i]);
    }
}

• 思路二 二分查找法的运用

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        
        if(nums1.size() == 0 || nums2.size() == 0){
            return result;
        }
        
        // 对数组排序, 满足二分查找的前提条件
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        for(int i=0; i < nums1.size(); i++){
            int tt = BinarySearch(nums2, 0, nums2.size()-1, nums1[i]);
            if(tt >= 0){
                result.push_back(nums1[i]);
                nums2.erase(nums2.begin() + tt);
            }
        }
        return result;
    }
    
     int BinarySearch(vector<int>& 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 indexOfmed;
            }
        }
        else{
            return -1;
        }
    }
};

• 思路三 运用map存储哈希值，其中key为数组数字，value为数字个数

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        map<int, int> mp;
        
        if(nums1.size() == 0 || nums2.size() == 0){
            return result;
        }
        
        for(int i=0; i < nums1.size(); i++){
            // 发现重复值
            if(mp.find(nums1[i]) != mp.end()){
                mp[nums1[i]]++;
            }
            else{ // 没有发现重复值
                mp[nums1[i]] = 1;            
            }
        }
        
        for(int i=0; i < nums2.size(); i++){
            if(mp.find(nums2[i]) != mp.end() && mp[nums2[i]] > 0){
                result.push_back(nums2[i]);
                mp[nums2[i]]--;
            }
        }
        return result;
    }
};

思考