540. Single Element in a Sorted Array

Problem

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.

https://leetcode.cn/problems/single-element-in-a-sorted-array/

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 <= 10^5
0 <= nums[i] <= 10^5

Test Cases

1 2	class Solution: def singleNonDuplicate(self, nums: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('nums, expected', [
    ([1,1,2,3,3,4,4,8,8], 2),
    ([3,3,7,7,10,11,11], 10),

    ([6], 6),
])
class Test:
    def test_solution(self, nums, expected):
        sol = Solution()
        assert sol.singleNonDuplicate(nums) == expected

Thoughts

限制了 O(log n) 时间，加上数组是有序的，考虑二分法。

n 一定是个奇数，假设 n = 2 * m + 1

用正中位置把数组分成三份：左边 m 个数，正中的数，右边 m 个数。

如果正中的数与其左边和右边都不相等，那就是 the single element。

否则假设它跟左半边的最后一个数字相同，排除掉该数字后，剩下左边 m-1 个数，右边 m 个数。

目标 single element 在哪边，哪边的元素个数就是奇数，对那边的子数组重复类似的操作即可。

时间复杂度 O(log n)，空间复杂度 O(1)。

Code

solution.py

from typing import List


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        l, r = 0, len(nums)
        while l < r - 1:
            m = (l + r) >> 1
            v_l, v, v_r = nums[m-1:m+2]
            if v_l != v != v_r:
                return v

            if (m - l) & 1 == 0:
                # Even elements in each half array.
                if v == v_l:
                    # v_l is not single, remove it, then left half remains odd elements, check left half.
                    r = m - 1
                else:
                    # Otherwise, check right half.
                    l = m + 2
            else:
                # Odd elements in each half array.
                if v == v_l:
                    # v_l is not single, remove it, then right half still has odd elements, check right half.
                    l = m + 1
                else:
                    # Otherwise, check left half.
                    r = m

        return nums[l]

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。