Mind palace

some thoughts

0%

540. Single Element in a Sorted Array

Posted on Edited on In Disqus:
Symbols count in article: 770 Reading time ≈ 1 mins.

二分 O(logn) time O(1) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == nums[m + 1]) {
                if (m & 1) {
                    r = m - 1;
                } else {
                    l = m + 2;
                }
            } else {
                if (m & 1) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
        }
        return nums[l];
    }
};

too smart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] == nums[m ^ 1]) { // 任一数m异或1得到其相邻的数，偶数则是相邻较大的奇数，奇数则是相邻较小的偶数
                l = m + 1; // 如果相邻两数相等，则所求的数肯定在右侧，因为两个数左边是偶数个数右边是奇数个数
            } else { // 如果相邻两数不等，则所求的数要不是nums[m]要不在左侧
                r = m;
            }
        }
        return nums[l];
    }
};