題目描述 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

題目解讀

• 找到兩個(gè)數(shù)組的交集并返回

解題思路

• 1掂骏，首先用冒泡排序?qū)蓚€(gè)數(shù)組分別按照遞增排序
• 2，取出數(shù)組1中的每一個(gè)數(shù)字，用二分查找方法去數(shù)組2中查找，如果找到則返回1，否則返回0
• 3乞旦，如果找到則將查找的這個(gè)數(shù)字放到待返回的數(shù)組中

Code

# include<stdio.h>

// 冒泡排序
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++實(shí)現(xiàn)

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        
        if(nums1.size() == 0 || nums2.size() == 0){
            return result;
        }
        
        // 對(duì)數(shù)組排序, 滿足二分查找的前提條件
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        
        // 對(duì) 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<int>& 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<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 true;
            }
        }
        else{
            return false;
        }
    }
};

• 思路三 STL中set方法

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> temp;
        vector<int> result;
        
        // 如果有一個(gè)數(shù)組甚至兩個(gè)數(shù)組輸入為空民逼，則返回交集為空
        if(nums1.size() == 0 || nums2.size() == 0){
            return result;
        }
        
        // 將數(shù)組nums1加入set集合中，注意此處加入的過(guò)程中自動(dòng)去掉重復(fù)值
        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 這么長(zhǎng)的原因，應(yīng)該是遞歸的使用调缨，遞歸很耗費(fèi)時(shí)間的４辍！弦叶！