【LeetCode】Day93-两个数组的交集 II

题目

350. 两个数组的交集 II【简单】

题解

哈希表

哈希表中统计nums1的元素和数量，再在nums2中查找

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        int n1=nums1.length,n2=nums2.length;
        int[] res=new int[Math.min(n1,n2)];
        Map<Integer,Integer>hashMap=new HashMap<>();
        //哈希表存储nums1的元素个数
        for(int i=0;i<n1;i++){
    
            if(hashMap.containsKey(nums1[i])){
    
                int count=hashMap.get(nums1[i])+1;
                hashMap.put(nums1[i],count);
            }
            else
                hashMap.put(nums1[i],1);
        }
        //nums2在哈希表中找交集
        int k=0;
        for(int i=0;i<n2;i++){
    
            if(hashMap.containsKey(nums2[i])){
    
                int count=hashMap.get(nums2[i]);
                if(count>0){
    
                    hashMap.put(nums2[i],count-1);
                    res[k++]=nums2[i];
                } 
            }
        }
        //数组截取
        return Arrays.copyOfRange(res, 0, k);
    }
}

时间复杂度：$O(m+n)$

空间复杂度：$O(min(m,n))$

排序+双指针

首先对两个数组排序，
之后根据nums1[i]和nums2[j]的大小移动指针 i 和 j 的位置，谁的元素小谁的指针后移一位；若元素相等，则记入结果数组

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        int n1=nums1.length,n2=nums2.length;
        int[] res=new int[Math.min(n1,n2)];
        //数组排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        //双指针
        int i=0,j=0,k=0;
        while(i<n1&&j<n2){
    
            if(nums1[i]==nums2[j]){
    
                res[k++]=nums1[i++];
                j++;
            }
            else if(nums1[i]<nums2[j])
                i++;
            else
                j++;
        }
        //数组截取
        return Arrays.copyOfRange(res, 0, k);
    }
}

时间复杂度：$O(mlogm+nlogn)$，排序所需的时间复杂度

空间复杂度：$O(min(m,n))$，为返回值创建一个数组 res，其长度为较短的数组的长度。

虽然看上去方法二看上去更聪明一点，但实际复杂度却不如方法一…