T540、有序数组中的唯一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

解

有序这一条件是多余的。对偶数位进行二分查找，确保中间位mid是偶数（奇数的话减一）。如果mid和mid+1的值相等说明唯一数在右边，否则在左边。

 public int singleNonDuplicate(int[] nums) {
        if(nums.length<1)
            return 0;
        int i = 0, j = nums.length - 1;
        while(i < j){
            int mid = i + (j - i) / 2;
            if(mid % 2 == 1)
                mid--;
            if(nums[mid] == nums[mid+1])
                i = mid + 2;
            else 
                j = mid;
        }
        return nums[j];
    }

解2

二分查找是除去中间的2个相同数，则唯一数在奇数的一方

 public int singleNonDuplicate(int[] nums) {
        if(nums.length<1)
            return 0;
        int i = 0, j = nums.length - 1;
        while(i < j){
            int mid = i + (j - i) / 2;
            if(nums[mid]==nums[mid+1]){
                if((mid-1-i+1) % 2 ==1)
                    j = mid-1;
                else 
                    i = mid + 2;
            }else if(nums[mid]==nums[mid-1]){
                if((mid-2-i+1) % 2 ==1)
                    j = mid-2;
                else 
                    i = mid + 1;
            }else
                return nums[mid];
        }
        return nums[j];
    }