548.Intersection of Two Arrays II

1.Description(Easy)

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

Notice

• Each element in the result should appear as many times as it shows in both arrays.

• The result can be in any order.

Example

Givennums1=[1, 2, 2, 1],nums2=[2, 2], return[2, 2].

2.Code

Version 1: HashMap (Time exceed)

public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1==null || nums2==null){
            return null;
        }
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int i=0;i<nums1.length;i++){
            if(!map.containsKey(nums1[i])){
                map.put(nums1[i], 1);
            }else{
                map.put(nums1[i],map.get(nums1[i])+1);
            }
        }

        ArrayList<Integer> list=new ArrayList<Integer>();
        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);
            }
        }

        int[] result=new int[list.size()];
        for(int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        return result;
    }

Version 2: Sort+Two pointer

public int[] intersection2(int[] nums1, int[] nums2){
        if(nums1==null || nums2==null){
            return null;
        }
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int index1=0;
        int index2=0;
        ArrayList<Integer> list=new ArrayList<Integer>();
        while(index1<nums1.length && index2<nums2.length){
            if(nums1[index1]>nums2[index2]){
                index2++;
            }else if(nums1[index1]<nums2[index2]){
                index1++;
            }else{
                list.add(nums1[index1]);
                index1++;
                index2++;
            }

        }
        int[] result=new int[list.size()];
        for(int i=0;i<list.size();i++){
            result[i]=list.get(i);
        }
        return result;
    }