Using Collections.binarySearch (for fun)


  • 3

    Longer than writing my own binary search, but I wanted to see how this would look. I let Collections.binarySearch search in a special List object which returns -1 for indexes before the single element, 0 for the index of the single element, and 1 for indexes after the single element. So I run binary search for 0. Since my special List object computes its entries only on the fly when requested, this solution takes O(log n) time and O(1) space.

    public int singleNonDuplicate(int[] nums) {
        List list = new ArrayList() {
            public int size() {
                return nums.length;
            }
            public Integer get(int index) {
                if ((index ^ 1) < size() && nums[index] == nums[index ^ 1])
                    return -1;
                if (index == 0 || index % 2 == 0 && nums[index - 1] != nums[index])
                    return 0;
                return 1;
            }
        };
        return nums[Collections.binarySearch(list, 0)];
    }
    

    A variation, the helper isOff tells whether the index is in the part that's "off" (the single element and everything after it):

    public int singleNonDuplicate(int[] nums) {
        List list = new ArrayList() {
            public int size() {
                return nums.length;
            }
            public Integer get(int index) {
                return isOff(index) + isOff(index - 1);
            }
            int isOff(int i) {
                return i == size() - 1 || i >= 0 && nums[i] != nums[i ^ 1] ? 1 : 0;
            }
        };
        return nums[Collections.binarySearch(list, 1)];
    }

Log in to reply
 

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