题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

题目链接

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

示例

示例1

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例2

输入: [3,3,7,7,10,11,11]
输出: 10

题目分析

此题如果不考虑附加要求，十分简单，遍历一次即可。时间复杂度O(n)，空间复杂度O(1)。

考虑附加要求。由于题目数组除了单一元素以外的其他元素都会出现两次，因此数组元素个数必然是奇数。

由于题目要求的复杂度是O(log n)，所以考虑使用二分法来解决。利用双指针划分数组：

int left = 0;
int right = numsSize - 1;
mid = (left + right + 1) / 2;

找到中间索引后，检查中间索引的两侧元素与中间元素是否相等：

• 如果nums[mid] == nums[mid - 1]，检验中间元素两侧的元素个数。
• 如果nums[mid] == nums[mid + 1]，检验中间元素两侧的元素个数。
• 如果都不相等，那么说明中间元素就是那个不重复的元素。

解释一下检验中间元素两侧的元素个数，以示例1作为样本。

初始数组：

中间元素：

将中间元素与其前一位对比，发现相等，现在的数组：

左侧元素个数是3个，右侧元素是4个。

由于题目的数组只有一个元素是单独的，而其他元素都是有且只有2个，那么在原数组基础上删掉两次相同的元素后，剩下的元素依然是这样2m+n的形式搭配。

因此，在本题中的子数组如果个数为偶数，那么单一元素一定不在这个子数组中，将之抛弃即可。

if (nums[mid] == nums[mid - 1]){
    if ((left + mid - 1) % 2 == 0){
        left = mid + 1;
    }else {
        right = mid - 2;
    }
}else if (nums[mid] == nums[mid + 1]){
    if ((left + mid) % 2 == 0){
        left = mid + 2;
    }else {
        right = mid - 1;
    }
}else return nums[mid];

题目解答

int singleNonDuplicate(int* nums, int numsSize){
    int left = 0;
    int right = numsSize - 1;

    while (left < right){
        int mid = (left + right) / 2;
        if (nums[mid] == nums[mid - 1]){
            if ((left + mid - 1) % 2 == 0) {
                left = mid + 1;
            }else {
                right = mid - 2;
            }
        }else if (nums[mid] == nums[mid + 1]){
            if ((mid + left) % 2 == 0){
                left = mid + 2;
            }else {
                right = mid - 1;
            }
        }else {
            return nums[mid];
        }
    }

    return nums[right];
}