Java O(nlgn) Binary Search Solution Beat 96%


  • 0
    P

    Sort two array, loop through all elements in one array, ignore the duplicate elements and use binary search to check with another array. keep the result on the current array then transfer onto the result in the end.

    So it would take O(nlogn) time for sorting and loop through the array with binary search, and take O(1) space if we ignore the output array.

      public int[] intersection(int[] nums1, int[] nums2) {
            
            if(nums1.length == 0 || nums2.length == 0){return new int[0];}
            
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            
            int index = 0;
            int prev = 0;
            
            for (int i = 0; i < nums2.length; i++){
                
                if(nums2[i] == prev && i != 0){
                    continue;
                }
                
                if(binarySearch(nums1, nums2[i])){
                    nums2[index] = nums2[i];
                    index++;
                }
                
                prev = nums2[i];
            }
            
            int[] rst = new int[index];
            
            for (int i = 0; i < index; i++){
                rst[i] = nums2[i];
            }
            
            return rst;
            
        }
        
        private static boolean binarySearch(int[] nums, int a){
            int i = 0, j = nums.length - 1;
            
            while (i + 1 < j){
                int mid = i + (j - i) / 2;
                if (nums[mid] == a){
                    return true;
                }else if(nums[mid] < a){
                    i = mid;
                }else{
                    j = mid;
                }
            }
            
            if(nums[i] == a || nums[j] == a){return true;}
            
            return false;
        }
    

Log in to reply
 

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