Need help to explain why second approach(4ms) beat first one(8ms)


  • 0
    X

    First approach

    • Initialize two sets to eliminate duplicate elements from nums1 and nums2, take O(n)
    • Traverse setB in order to find element i in setA, takes O(length of setB)
    • Save result for output
    public int[] intersection4(int[] nums1, int[] nums2) {
        if (nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> setA = new HashSet<>();
        for (int i : nums1)
            setA.add(i);
    
        Set<Integer> setB = new HashSet<>();
        for (int i : nums2)
            setB.add(i);
    
        int[] result = new int[nums1.length];
        int index = 0;
        for (int i : setB) {
            if (setA.contains(i))
                result[index++] = i;
        }
        return Arrays.copyOfRange(result, 0, index);
    }
    

    Second approach

    • Sort two arrays with O( nlgn )
    • For binary search takes O( lgn)
    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 r[] = new int[Math.min(nums1.length, nums2.length)];
        int c = 0;
        for (int i : nums1) {
            if (c == 0 || i != r[c - 1]) {
                if (Arrays.binarySearch(nums2, i) >= 0) {
                    r[c++] = i;
                }
            }
        }
        
        return Arrays.copyOf(r, c);
    }
    

    Thanks for your help in advance.


Log in to reply
 

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