6ms solution with binary search


  • 0
    H
    public int[] intersect(int[] nums1, int[] nums2) {
        int [] result = {};
        int [] shorter;
        int [] longer;
    
        if (nums1.length > 0 && nums2.length > 0) {
            if (nums1.length < nums2.length) { 
                shorter = nums1; 
                longer = nums2; 
            }
            else {
                shorter = nums2; 
                longer = nums1;
            }
            BitSet used = new BitSet(shorter.length);
            Arrays.sort(shorter);
            int next = -1;
            int prev = -1;
            for (int i = 0; i < longer.length; i++) {
                int pos = Arrays.binarySearch(shorter, longer[i]);
                if (pos >= 0) {
                    if (!used.get(pos)) {
                        used.set(pos, true);
                    } else {
                        next = used.nextClearBit(pos + 1);
                        if (next > 0 && next < shorter.length && shorter[next] == longer[i]) {
                            used.set(next, true);
                        } else {
                            prev = used.previousClearBit(pos - 1);    
                            if (prev >=0 && shorter[prev] == longer[i]) {
                                used.set(prev, true);
                            }
                        }
                    }
                    
                }
            }
            result = new int[used.cardinality()];
            next = used.nextSetBit(0);
            int j = 0;
            while(next >= 0) {
                result[j++] = shorter[next];
                next = used.nextSetBit(next + 1);
            }
        }
        
        return result;
    }

  • 0
    H

    Only shorter list has been sorted.
    BitSet used - contains indexes of numbers from shorter list which appeared in longer list


Log in to reply
 

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