LeetCode Solutions

Appearance

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

为保证权益，题目请参考 540. 有序数组中的单一元素(From LeetCode).

解决方案1 ​

Python ​

python
# 540. 有序数组中的单一元素
# https://leetcode-cn.com/problems/single-element-in-a-sorted-array/


from typing import List


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

        n = (len(nums) + 1 ) // 2
        l = 0
        r = n - 1

        ans = 0
        while l <= r:
            m = (l+r) // 2
            if ((2 * m + 1) >= len(nums) or ((2 * m + 1) < len(nums) and nums[m*2] != nums[m*2 + 1])) \
                    and (m == 0 or (nums[m*2] != nums[m*2 - 1])):
                ans = nums[m*2]
                break
            if nums[m*2] == nums[m*2 + 1]:
                l = m + 1
            else:
                r = m - 1

        return ans


if __name__ == "__main__":
    solution = Solution()
    print(solution.singleNonDuplicate([3,3, 7,7,10,10,11]))

解决方案2 ​

Python ​

python
from typing import List


class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        l = 0
        r = n - 1

        while l < r:
            m = (l + r) // 2

            if nums[m] == nums[m ^ 1]:
                l = m + 1
            else:
                r = m

        return nums[l]