两个数组的交集 II

给定两个数组，写一个方法来计算它们的交集。

例如:
给定 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

注意：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
跟进:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果nums2的元素存储在磁盘上，内存是有限的，你不能一次加载所有的元素到内存中，你该怎么办？

思路1

一个个遍历，遇到相同的数，将其加入集合，将这个数与数组最后一位交换，该数组的长度减一

实现代码

C语言

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int k=0;
   
    int *result=(int *)malloc(nums2Size*sizeof(int));
    for(int i=0;i<nums1Size;++i){
        for(int j=0;j<nums2Size;++j){
            
            if(nums1[i]==nums2[j]){
                
                if(nums2Size>0){
                    result[(*returnSize)++]=nums1[i];
                    int temp=nums2[j];
                    nums2[j]=nums2[nums2Size-1];
                    nums2[nums2Size-1]=temp;
                    nums2Size--;
                }
                
            break;
            }
        }
    }
    
    return result;
}

实现代码

Java

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int returnSize[];
    
    List<Integer> list=new ArrayList<Integer>();
    
    int nums2Size=nums2.length;
    for(int i=0;i<nums1.length;++i){
        for(int j=0;j<nums2Size;++j){
            
            if(nums1[i]==nums2[j]){
                
                if(nums2Size>0){
                    list.add(nums1[i]);
                    int temp=nums2[j];
                    nums2[j]=nums2[nums2Size-1];
                    nums2[nums2Size-1]=temp;
                    
                    nums2Size--;
                }
                
                break;
            }
        }
    }
        int[] result = new int[list.size()];
        int i = 0;
        for (Integer e : list)
              result[i++] = e;
        return result;
    }
}

思路2

用HashMap存储第一个数组，key为数组的值，value为该值出现次数，然后用该map去遍历第二个数组，如果查到有这个键，则将该键放到list，值减一

实现代码

HashMap<Integer, Integer> map=new HashMap<Integer, Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<nums1.length;++i) {
            if(map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i])+1);
            }else {
                map.put(nums1[i], 1);
            }
        }
        
        for(int i=0;i<nums2.length;++i) {
            if(map.containsKey(nums2[i])&&map.get(nums2[i])>0) {
                list.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i])-1);
            }else {
                
            }
        
         
        }
        
        int[] result=new int[list.size()];
        for(int i=0;i<list.size();++i) {
            result[i]=list.get(i);
        }
            
            
        return result;  

    }

思路3

对两个数组进行排序，然后对两个数组进行比较，小的一方下标加1，相等时两个数组下标都加1。

实现代码

Java

Arrays.sort(nums1);
        Arrays.sort(nums2);
        ArrayList<Integer> list = new ArrayList<Integer>();
        int i=0,j=0;
        while(i<nums1.length&&j<nums2.length){
            if(nums1[i]==nums2[j]){
                list.add(nums1[i]);
                ++i;
                ++j;
            }
            else if(nums1[i]>nums2[j]){
                ++j;
            }
            else{
                ++i;
            }
        }
        int[] result=new int[list.size()];
        for(int k=0;k<list.size();++k) {
            result[k]=list.get(k);
        }
        return result;  

C语言

int partition(int arr[], int low, int high){
    int key;
    key = arr[low];
    while(low<high){
        while(low <high && arr[high]>= key )
            high--;
        if(low<high)
            arr[low++] = arr[high];
        while( low<high && arr[low]<=key )
            low++;
        if(low<high)
            arr[high--] = arr[low];
    }
    arr[low] = key;
    return low;
}
void quick_sort(int arr[], int start, int end){
    int pos;
    if (start<end){
        pos = partition(arr, start, end);
        quick_sort(arr,start,pos-1);
        quick_sort(arr,pos+1,end);
    }
    
}

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
     quick_sort(nums1,0,nums1Size-1);
     quick_sort(nums2,0,nums2Size-1);
  
     int size = nums1Size<nums2Size?nums1Size:nums2Size;
     int *result=(int *)malloc(size*sizeof(int));
    //memset(result,0,sizeof(int)*size);
     
     int i=0,j=0,z=0;
        while(i<nums1Size&&j<nums2Size){
            if(nums1[i]==nums2[j]){
                result[z]=nums1[i];
                ++i;
                ++j;
                ++z;
            }
            else if(nums1[i]>nums2[j]){
                ++j;
            }
            else {
                ++i;
            }
        }
     *returnSize=z;
     return result;
}