How can I solve the Single Element in a Sorted Array problem?

Use binary search to efficiently narrow down the half of the array where the unique element exists, while ensuring O(log n) time complexity.

What is the time complexity of solving the problem?

The time complexity of the optimal solution is O(log n) due to the binary search method.

Can I solve this problem with a hashmap?

While using a hashmap is possible, it would result in O(n) time complexity and does not satisfy the problem's constraints of O(log n) time.

How do I handle edge cases like arrays with only one element?

For arrays with one element, simply return that element as it is the unique one.

What is the primary algorithmic pattern in the Single Element in a Sorted Array problem?

The main pattern is binary search over the valid answer space, focusing on the structure of the sorted array to efficiently find the unique element.

#540

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。请你找出并返回只出现一次的那个数。你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。示例 1: 输入: nums = [1,1,2,3,3,4,4,8,8] 输出: 2 示例 2: …

数组二分查找

题目描述

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

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

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

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

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

提示:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

lightbulb

解题思路

方法一：二分查找

题目给定的数组 $\textit{nums}$ 是有序的，且要求在 $\textit{O}(\log n)$ 时间找到只出现一次的元素，因此我们考虑使用二分查找解决。

我们定义二分查找的左边界 $\textit{l} = 0$ ，右边界 $\textit{r} = n - 1$ ，其中 $n$ 是数组的长度。

在每一步中，我们取中间位置 $\textit{mid} = (l + r) / 2$ ，如果下标 $\textit{mid}$ 为偶数，那么我们应该将 $\textit{nums}[\textit{mid}]$ 与 $\textit{nums}[\textit{mid} + 1]$ 进行比较；如果下标 $\textit{mid}$ 为奇数，那么我们应该将 $\textit{nums}[\textit{mid}]$ 与 $\textit{nums}[\textit{mid} - 1]$ 进行比较。因此，我们可以统一将 $\textit{nums}[\textit{mid}]$ 与 $\textit{nums}[\textit{mid} \oplus 1]$ 进行比较，其中 $\oplus$ 表示异或运算。

如果 $\textit{nums}[\textit{mid}] \neq \textit{nums}[\textit{mid} \oplus 1]$ ，那么答案在 $[\textit{l}, \textit{mid}]$ 中，我们令 $\textit{r} = \textit{mid}$ ；如果 $\textit{nums}[\textit{mid}] = \textit{nums}[\textit{mid} \oplus 1]$ ，那么答案在 $[\textit{mid} + 1, \textit{r}]$ 中，我们令 $\textit{l} = \textit{mid} + 1$ 。继续二分查找，直到 $\textit{l} = \textit{r}$ ，此时 $\textit{nums}[\textit{l}]$ 即为只出现一次的元素。

时间复杂度 $\textit{O}(\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。空间复杂度 $\textit{O}(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1
        while l < r:
            mid = (l + r) >> 1
            if nums[mid] != nums[mid ^ 1]:
                r = mid
            else:
                l = mid + 1
        return nums[l]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates an understanding of binary search on sorted arrays.
question_mark
Candidate can correctly identify the relationship between array splitting and pair identification.
question_mark
Candidate handles edge cases such as arrays with only one element and arrays with unique elements at the boundaries.

warning

常见陷阱

外企场景

error
Forgetting the O(log n) time complexity requirement and attempting brute force methods.
error
Misunderstanding the array's structure and mistakenly assuming multiple unique elements exist.
error
Failing to account for edge cases, especially small arrays or unique elements at the boundaries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider solving the problem in O(n) time with a hashmap, but note that this doesn’t satisfy the time complexity requirement.
arrow_right_alt
Change the problem to a rotated sorted array where binary search still applies but requires adjusted logic.
arrow_right_alt
Extend the problem to find multiple non-duplicate elements in a sorted array, requiring a different strategy.

help

常见问题

外企场景

继续练习

#532 数组中的 k-diff 数对 #528 按权重随机选择 #497 非重叠矩形中的随机点