Java code w/ binary search, easy to understand


  • 0
    A
    public class Solution {
    public int singleNonDuplicate(int[] nums) {
        // algorithm 2017/07/20: A smarter algorithm is to do a binary search
        // check the middle number: if it is different from both left and right number, then the middle number is the result
        // if it is the same as the number on one side, we just need to check how many numbers are on this side
        /*
          1 1 2 2 3
        1 1 2 2 3 3 4
          1 2 2 3 3
        1 2 2 3 3 4 4
        */
        int left = 0, right = nums.length-1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1]) {
                return nums[mid];
            } else if (nums[mid] == nums[mid-1]) {
                // middle number is equal to the one on left
                if (1 == mid % 2 ) {
                    left = mid + 1;     // singleNumber is on the right
                } else {
                    right = mid - 2;    // singleNumber is on the left. -2 because mid and mid-1 are same
                }
            } else {
                // middle number is equal to the one on right
                if (1 == mid % 2) {
                    right = mid - 1;     // singleNumber is on the left
                } else {
                    left = mid + 2;    // single number is on the right
                }
            }
        }
        return nums[left];  // lower bound        
    }
    

    }


Log in to reply
 

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