leetcode刷题（五）——找出数组中唯一出现的数

        给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:

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

提示:

1 <= nums.length <= 105
0 <= nums[i] <= 105

思路1：一个数异或自己本身结果为0

int singleNonDuplicate(int* nums, int numsSize){
    int ret = 0;
    for(int i=0;i<numsSize;i++)
        ret ^= nums[i];
    return ret;
}

思路2：遍历

int singleNonDuplicate(int* nums, int numsSize)
{
    for(int i=0;i<numsSize;i++)
    {
        printf("%d\n",num[i]);
        int count=0
        for(int j=0;j<numsSize;j++)
        {
            if(nums[i]=nums[i-1])
            {
                count++;
            }
        }
        if(count==1)
        {
            return num[i];
        } 
    }
    return -1;
}

思路3：二分法

int singleNonDuplicate(int* nums, int numsSize){
    //二分法
    int left = 0;
    int right = numsSize - 1;
    int mid = 0;
    if (numsSize == 0)
        return 0;

    while (left < right)
    {
        mid = left + (right - left) / 2;
        if (mid & 1)
        {
            if (*(nums + mid) == *(nums + mid + 1))
                                       //mid为奇数，与mid右边的数相同，唯一数在mid左边
                right = mid - 1;
            else if (*(nums + mid) == *(nums + mid - 1))
                                       //mid-1为偶数，mid与mid左边的数相同，唯一数在mid右边
                left = mid + 1;
            else                                        
                                        //与左右俩边的都不同，mid对应的就是唯一数
                return *(nums + mid);
        }
        else
        {
            if (*(nums + mid) == *(nums + mid + 1))
                                        //mid为偶数，与mid右边的数相同，唯一数在mid右边
                left = mid + 2;
            else if (*(nums + mid) == *(nums + mid - 1))
                                      //mid - 1为奇数，mid与mid左边的数相同，唯一数在mid左边
                right = mid - 2;
            else                                        
                                        //mid与左右俩边数都不相同，则mid对应的数就是唯一数
                return *(nums + mid);
        }
    }
    return *(nums + left);
}

如果是三次呢？

int singleNumber(int *nums, int numsSize) {
    int a = 0, b = 0;
    for (int i = 0; i < numsSize; i++) {
        b = ~a & (b ^ nums[i]);
        a = ~b & (a ^ nums[i]);
    }
    return b;
}