Three ways in Java: HashMap, sort one array, sort two arrays


  • 0
    F

    sort one array

    sort the smaller array, then use a boolean array to mark whether this element in sorted array had been taken away. If we find an element equal to what we want, but has been taken away, then we find it in it's left or right surroundings.

    public class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            if(nums1.length<nums2.length){//make nums2 to be smaller
                int[] tmp=nums2;
                nums2=nums1;
                nums1=tmp;
            }
            Arrays.sort(nums2);
            boolean tag[]=new boolean[nums2.length];/mark every element whether be taken away
            ArrayList<Integer> list=new ArrayList<>(nums2.length);
            for(int i:nums1){
                if(binarySearch(nums2,i,tag)){
                    list.add(i);
                }
            }
            int[] res=new int[list.size()];
            for(int i=0;i<list.size();i++){
                res[i]=list.get(i);
            }
            return res;
        }
        
        private boolean binarySearch(int[] nums2,int i,boolean[] tag){
            int left=0,right=nums2.length-1;
            while(left<=right){
                int mid=left+(right-left)/2;
                if(nums2[mid]>i){
                    right=mid-1;
                }else if(nums2[mid]<i){
                    left=mid+1;
                }else{
                    if(tag[mid]==false){//haven't been taken away
                        tag[mid]=true;
                        return true;
                    }else{//find equal element in left or right
                        int p=mid+1,q=mid-1;
                        while(p<nums2.length&&nums2[p]==i&&tag[p]==true){
                            p++;
                        }
                        if(p==nums2.length){
                            return false;
                        }
                        if(nums2[p]==i){
                            tag[p]=true;
                            return true;
                        }
                        
                        while(q>=0&&nums2[q]==i&&tag[q]==true){
                            q--;
                        }
                        if(q==-1){
                            return false;
                        }
                        if(nums2[q]==i){
                            tag[q]=true;//mark as taken
                            return true;
                        }
                        return false;
                    }
                }
            }
            return false;
        }
    }
    
    

    sort two arrays

    public class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int i=0,j=0;
            int maxLength=nums1.length<nums2.length?nums1.length:nums2.length;
            ArrayList<Integer> list=new ArrayList<>(maxLength);
            while(i<nums1.length&&j<nums2.length){
                if(nums1[i]==nums2[j]){
                    list.add(nums1[i]);
                    i++;
                    j++;
                }else if(nums1[i]<nums2[j]){
                    i++;
                }else{
                    j++;
                }
            }
            int[] res=new int[list.size()];
            for(i=0;i<list.size();i++){
                res[i]=list.get(i);
            }
            return res;
        }
    }
    

    use HashMap to record frequency

    public class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            HashMap<Integer,Integer> map1=new HashMap<>(nums1.length);
            HashMap<Integer,Integer> map2=new HashMap<>(nums2.length);
            for(int i:nums1){
                if(map1.containsKey(i)){
                    int freq=map1.get(i)+1;
                    map1.put(i,freq);
                }else{
                    map1.put(i,1);
                }
            }
            for(int i:nums2){
                if(map2.containsKey(i)){
                    int freq=map2.get(i)+1;
                    map2.put(i,freq);
                }else{
                    map2.put(i,1);
                }
            }
            int l=(nums1.length<nums2.length?nums1.length:nums2.length);
            ArrayList<Integer> list=new ArrayList(l);
            for(int i: map1.keySet()){
                if(map2.containsKey(i)){
                    int c1=map1.get(i);
                    int c2=map2.get(i);
                    int count=c1<c2?c1:c2;
                    while(count-->0){
                        list.add(i);
                    }
                }
            }
            int[] res=new int[list.size()];
            for(int i=0;i<list.size();i++){
                res[i]=list.get(i);
            }
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.