每日一题——540. 有序数组中的单一元素

540. 有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

---

主要考虑二分 就是二分的条件有点别扭

我也是看了一会才看懂怎么二分

因为是有序数组 相等的元素一定相邻

1 1 2 3 3 4 4 8 8

对于2来说 他左边有2个数 右边有6个数

推广一下单个数左右两边的元素一定是偶数

对于下标 0 1  2  3 4  5 6  7 8来说

也就是单元素的下标必定是偶数 且一定跟上一个和下一个都不相等

我们的目标就是要通过二分来找到这样的元素

那就判断呗

对于单元素的左边 下标x = x+1 那x一定是偶数

对于单元素的右边 下标y = y+1 那y一定是个奇数

mid是偶数，那就比较mid和mid+1

mid是奇数，就比较mid-1和mid

如果相等 就证明mid在单元素左边

如果不相等 就证明mid在单元素右边

一直到两个重叠了为止

public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.Length - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            //二分经典中点不越界写法
            if(mid % 2 == 0)
            {
                if(nums[mid] == nums[mid+1])
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
            else
            {
                if(nums[mid-1] == nums[mid])
                {
                    left++;
                }
                else
                {
                    right--;
                }
            }
        }
        return nums[left];
    }
}