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

链接：540.有序数组中的单一元素
难度：Medium
标签：数组、二分查找
简介：给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。

题解 1 - python

• 编辑时间：2024-11-10
• 执行用时：4ms
• 内存消耗：23.52MB
• 编程语言：python
• 解法介绍：遍历时用异或去重。

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        return reduce(lambda a, b: a ^ b, nums, 0)

题解 2 - cpp

• 编辑时间：2022-02-14
• 执行用时：20ms
• 内存消耗：21.9MB
• 编程语言：cpp
• 解法介绍：bs, 如果是偶数下标与后面的比，奇数下标与前面的比。

class Solution {
   public:
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1, m;
        while (l < r) {
            m = (l + r) >> 1;
            if (nums[m] == nums[m ^ 1])
                l = m + 1;
            else
                r = m;
        }
        return nums[l];
    }
};

题解 3 - cpp

• 编辑时间：2022-02-14
• 执行用时：16ms
• 内存消耗：21.9MB
• 编程语言：cpp
• 解法介绍：bs。

class Solution {
   public:
    int singleNonDuplicate(vector<int>& nums) {
        return bs(nums, 0, nums.size() - 1);
    }
    int bs(vector<int>& nums, int l, int r) {
        int n = r - l + 1, m = (l + r) >> 1;
        if (n == 1 || nums[l] != nums[l + 1]) return nums[l];
        if (nums[r] != nums[r - 1]) return nums[r];
        if (nums[m] != nums[m - 1] && nums[m] != nums[m + 1]) return nums[m];
        if (nums[m] == nums[m - 1]) m--;
        if ((m - l) & 1)
            return bs(nums, l, m - 1);
        else
            return bs(nums, m + 2, r);
    }
};