leetcode540. Single Element in a Sorted Array

题目要求

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly 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.

现有一个有序的递增的整数数组，其中除了一个数字之外，每个数字都出现了两次。要求用O(log n)的时间复杂度和O(1)的空间复杂度找出只出现一次的数字。

思路一：位运算

已知 a ^ a = 0，利用这个结论，可以对所有的数字执行异或操作，最终异或的结果就是只出现一次的数字。

public int singleNonDuplicate(int[] nums) {  
    int result = 0;  
    for (int num : nums) {  
        result ^= num;  
    }  
    return result;  
}

思路二：二分法

O(log n)的时间复杂度通常都和二分法有关，而这里的二分法的思考点在于如何寻找中间位置，以及用什么判断逻辑来决定是继续递归处理左子数字还是右子数组。

一旦找到合适的中间位置，我们就应该可以判断出来单个数字究竟是出现在左子数字还是右子数字。那么我们的目标就应该是找到中间的重复数对的第一个数字。假如我们默认左子数组中不存在单个数字，则说明中间数对应该是位于一个偶数下标上，如下：

0 1 2 3 4
1 1 3 3 5
    ^

但是假如单个数字在左子数组，则我们找到的中间位置偶数下标上的数字就不是重复数对的第一个下标

0 1 2 3 4
1 2 2 3 3
    ^

因此找到中间位置的偶数下标上的值，并且和后面的数字进行比较，就知道单个数字究竟在左边还是在右边。

public int singleNonDuplicate2(int[] nums) {  
    int start = 0, end = nums.length - 1;  
    while (start < end) {  
        int mid = (start + end) / 2;  
        //假设左半边子数组均为重复数字，则默认的中间数对的第一个数字的下标一定为偶数  
 //找到中间数对第一个数字的下标  
    if (mid % 2 == 0) {mid -= 1;}  
        //中间数对为重复数字，说明单个数字在右半边  
    if (nums[mid] == nums[mid + 1]) {  
            start = mid + 2;  
        } else {  
            end = mid - 1;  
        }  
    }  
    return start;  
}