欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

540. 有序数组中的单一元素——二分查找

程序员文章站 2024-03-17 16:34:40
...

传送门:https://leetcode-cn.com/problems/single-element-in-a-sorted-array/

题目

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

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

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

思路

一个仅由整数组成的、每个元素都会出现两次的有序数组,满足一下性质:

  • 每个元素必成对出现
  • 若下标x为偶数,则nums[x] = nums[x + 1]
  • 若下标x为奇数,则nums[x - 1] = nums[x]

如果在数组中有一个数只出现了一次
则在这个数左侧的子数组仍然满足上述性质
但这个数右侧的子数组的就不满足上述性质
所以,目标数的左右两侧有明显的性质差别,这就是运用二分查找的依据

每次对二分的mid做判断,如果满足上述性质就继续查找右侧,否则继续查找左侧。

技巧

官方题解有个判断上述性质的巧妙方法:

利用按位异或的性质,可以得到 mid和相邻的数之间的如下关系,其中 ⊕ 是按位异或运算符:
当mid是偶数, mid + 1 = mid ⊕ 1
当mid是奇数,mid - 1 = mid ⊕ 1
因此在二分查找的过程中,不需要判断 mid 的奇偶性,mid 和 mid ⊕1 即为每次需要比较元素的两个下标。

附官方题解代码

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (high - low) >> 1 + low;
            if (nums[mid] == nums[mid ^ 1]) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }
}

参考

官方题解:https://leetcode-cn.com/problems/single-element-in-a-sorted-array/solution/you-xu-shu-zu-zhong-de-dan-yi-yuan-su-by-y8gh/