my two pointers solution and the answers of the follow up questions.


  • 4

    What if the given array is already sorted? How would you optimize your algorithm?
    ==>two pointers

    What if nums1's size is small compared to nums2's size? Which algorithm is better?
    ==>hash map

    What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
    ==> binary search

    
        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            ArrayList<Integer> ret = new ArrayList<>();
            for(int i = 0, j = 0; i < nums1.length && j < nums2.length; ){
                if(nums1[i] < nums2[j]){
                    i++;
                }else if(nums1[i] > nums2[j]){
                    j++;
                }else{
                    ret.add(nums1[i]);
                    i++;
                    j++;
                }
            }
            int[] myret = new int[ret.size()];
            int index = 0;
            for(int num : ret){
                myret[index++] = num;
            }
            return myret;
        }
    
    

  • 0
    R

    could you explain your answers for followup2 and 3?


Log in to reply
 

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