540.single-element-in-a-sorted-array

Statement

简体中文English

Metadata

• Link: 有序数组中的单一元素
• Difficulty: Medium
• Tag: 数组 二分查找

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

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

你设计的解决方案必须满足 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 <= 105
• 0 <= nums[i] <= 105

Metadata

• Link: Single Element in a Sorted Array
• Difficulty: Medium
• Tag: Array Binary Search

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

 

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11]
Output: 10

 

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

Solution

Python 3

from bisect import bisect_left
from typing import List


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        return nums[bisect_left(range(n), 0, 0, n, key=lambda ix: -1 if (ix ^ 1) < n and nums[ix] == nums[ix ^ 1] else 0)]

---

最后更新: October 11, 2023