[leetcode] day93 - intersection of two arrays II

subject

350. Intersection of two arrays II【 Simple 】

Answer key

Hashtable

Statistics in hash table nums1 Elements and quantities of , And then nums2 Search for

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<>();
        // Hash table storage nums1 Number of elements of 
        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 Find the intersection in the hash table 
        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];
                } 
            }
        }
        // Array truncation 
        return Arrays.copyOfRange(res, 0, k);
    }
}

Time complexity ：$O(m+n)$

Spatial complexity ：$O(min(m,n))$

Sort + Double pointer

First, sort the two arrays ,
Then according to nums1[i] and nums2[j] Size of move pointer i and j The location of , Whose element is smaller, whose pointer moves back one bit ; If the elements are equal , Then it will be recorded in the result array

class Solution {
    
    public int[] intersect(int[] nums1, int[] nums2) {
    
        int n1=nums1.length,n2=nums2.length;
        int[] res=new int[Math.min(n1,n2)];
        // Array sorting 
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        // Double pointer 
        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++;
        }
        // Array truncation 
        return Arrays.copyOfRange(res, 0, k);
    }
}

Time complexity ：$O(mlogm+nlogn)$, The time complexity of sorting

Spatial complexity ：$O(min(m,n))$, Create an array of return values res, Its length is the length of the shorter array .

Although method two looks a little smarter , But the actual complexity is not as good as method 1 …