[LeetCode] 540. Single Element in a Sorted Array

时间:2021-09-26 20:30:26

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

Input: [1,1,2,3,3,4,4,8,8]
Output: 2

 

Example 2:

Input: [3,3,7,7,10,11,11]
Output: 10

 

Note: Your solution should run in O(log n) time and O(1) space.

 

题意:给一个排好序的数组,其中只有一个数字出现了1次,其余都出现了2次

二分的思想,这次判断的是奇偶,举个例子:

1) 1  1  2  3  3  4  4  8  8

二分先找中间,我们指向了nums[4] = =3 的位置,判断它的左右,找到第一个相同的数,什么意思呢,

我们假设现在数组是这样的

2)1  1  2  2  3  4  4  8  8           3的左和右都和它不等,那么3是我们要找的

假设数组现在是这样的

3)1  1  2  2  3  3  4  8  8           同1中做一下比较,1中第一个3的位置是3,从这个点起,左右两边(左边包括这个位置)哪边是奇数,那么那个只有1次的数字就在那边

这里注意一下,最左边和最右边有越界的情况,提前处理一下

class Solution {
    public int singleNonDuplicate(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        if (nums[0] != nums[1])
            return nums[0];
        int r = nums.length - 1;
        int l = 0;
        if (nums[r] != nums[r - 1])
            return nums[r];

        while (r - l > 5) {
            int mid = (r + l) / 2;
            if (nums[mid-1] != nums[mid] && nums[mid] != nums[mid+1])
                return nums[mid];
            if (nums[mid + 1] == nums[mid])
                mid ++;
            if ((mid - l + 1)%2 == 0)
                l = mid + 1;
            else
                r = mid;
        }
        if (l == 0)
            l++;
        if (r == nums.length - 1)
            r--;
        for (int i = l; i <= r; i++) {
            if (nums[i - 1] != nums[i] && nums[i] != nums[i + 1])
                return nums[i];
        }
        return 0;
    }
}