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?


  • 0
    L

    For the second answer, I'd saw you're wrong. It's faster to use list binary search


Log in to reply
 

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