这道题是很久以前的快手CPP面经中出现的，在此记录一下咋写

https://www.nowcoder.com/discuss/353156663853129728?sourceSSR=users

题目

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

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

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

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

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

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

思路

这道题如果用暴力遍历的话，O(N)的时间复杂度很容易搞定，比如遍历一遍用map记录一下每个元素出现的次数，再遍历一遍map就能得到结果。

但是题目要求是用O(log N)的时间复杂度，这就没有办法直接遍历了。但题目中给出的数组是有序的，再加上O(log N)的时间复杂度，这就需要我们能想到用二分法来解决这道题。

现在确定是用二分法了，具体怎么二分呢？这又不是比大小找元素！

先观察一下给出的数组，以示例一为例：

1
[1,1,2,3,3,4,4,8,8]

将这个数组中的2补全，即所有元素都出现两次

1
2
[1,1,2,2,3,3,4,4,8,8]
 0 1 2 3 4 5 6 7 8 9

能发现一个规律：奇数下标上的数和前一个数相同，偶数下标上的数和后一个数相同。

那么对于不符合条件的数组，我们只需要判断mid（数组中间）的元素

  • 如果mid是奇数，判断它是否和前一个数相同，如果相同，则能确定只出现一次的数是在mid的后边，不同则在mid之前；
  • 如果mid是偶数，判断它是否和后一个数相同，如果相同，则能确定只出现一次的数是在mid的后边，不同则在mid之前；

思路确定了，就可以写代码了

代码1-if/else

这里用if/else实现上述思路比较好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            // cout << left << " - " << right << " - " << mid << "\n";
            // 偶数
            if (mid % 2 == 0) {
                // 判断下一位是否和当前位相同
                if (nums[mid] == nums[mid + 1]) {
                    left = mid + 1; // 相同，在右边
                } else {            // 不相同，在左边
                    right = mid;
                }
            } else // 奇数
            {
                // 判断上一位是否和当前位相同
                if (nums[mid] == nums[mid - 1]) {
                    left = mid + 1; // 相同，在右边
                } else {            // 不相同，在左边
                    right = mid;
                }
            }
        }
        // 最终left所在位置就是题目需要的位置
        return nums[left];
    }
};

image-20240324111139325

代码2-位运算

使用位运算可以统一的处理奇数和偶数，代码能更加简洁。使用异或运算（相异为一相同为零）：

  • 奇数异或1等于奇数减一（奇数末尾为1，异或1后末尾为0，相当于减一）
  • 偶数异或1等于偶数加一（偶数末尾为0，异或1后末尾为1，相当于加一）

这样能写出如下代码，直接确定mid应该和谁进行比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            // 奇数异或1等于奇数减一，偶数异或1等于偶数加一
            if (nums[mid] == nums[mid ^ 1]) {
                left = mid + 1; // 在右边
            } else // 在左边
            {
                right = mid;
            }
        }
        return nums[left];
    }
};

image-20240324111454584