97.52 % O(n log n) Java solution, merging


  • 0
    A

    Make sure nums1 is the smaller (or equal) of the two.

    Sort both arrays

    Merge them but detect duplicates

    public class Solution {
        public int[] intersection(int[] nums1, int[] nums2) {
            if ( nums1.length > nums2.length ) {
                int[] temp = nums1;
                nums1 = nums2; 
                nums2 = temp;
            }
            if ( !isSorted(nums1) ) {
                Arrays.sort(nums1);
            }
            if ( !isSorted(nums2) ) {
                Arrays.sort(nums2);
            }
            int[] result = new int[nums1.length];
            int i = 0;
            int j = 0;
            int k = 0;
            while ( i < nums1.length && j < nums2.length ) {
                if ( nums1[i] == nums2[j] ) {
                    if ( k == 0 || result[k - 1] != nums1[i] ) {
                        result[k++] = nums1[i];
                    }
                    i++;
                    j++;
                } else if ( nums1[i] < nums2[j] ) {
                    i++;
                } else {
                    j++;
                }
            }
            return Arrays.copyOf(result, k);
        }
        
        private static boolean isSorted(int[] a) {
            for ( int i = 1; i < a.length; i++ ) {
                if ( a[i - 1] > a[i] ) { 
                    return false; 
                }
            }
            return true;
        }
    }

  • 0
    Z

    Perhaps you can delete the isSorted() funtion,


Log in to reply
 

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