540 Single Element in a Sorted Array

题目

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:

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

示例 2:

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

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

分析

由于所有元素已经排好了序，其实只要遍历所有元素，如果发现某个元素和前一个以及后一个都不一样，那么就找到了这个元素。当然，如果是第一个元素，则只需要判断和后一个是否不一样；而最后一个，只需要判断和倒数第二个是不一样。 这样是可以实现的，但是我们仔细一想，既然其他元素都是成双入对的，只有一个单的，不如让“成全”？我们对所有元素遍历并异或即可，因为相同的数异或等于0，最后的结果，就是我们要的被单下的元素了。

代码

int singleNonDuplicate(int* nums, int numsSize) {
    /*入参判断*/
    if(NULL == nums || 0 == numsSize)
        return 0;

    /*数量为1直接返回*/
    if(1 == numsSize)
        return nums[0];
    int loop = 0;
    int num = 0;
    /*遍历所有元素并异或*/
    for(loop = 0; loop < numsSize;loop++)
        num^=nums[loop];
    return num;
}