侧边栏壁纸
  • 累计撰写 19 篇文章
  • 累计创建 12 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

Leetcode每日一题-有序数组中的单一元素

whfree
2024-11-10 / 0 评论 / 0 点赞 / 9 阅读 / 2929 字

Leetcode每日一题-有序数组中的单一元素

原题链接:有序数组中的单一元素

这题是比较容易想到二分查找的解法,就只需要结合题意明确二分之后如何查找。稍微摸索一下规律可以发现:

只有一个数只出现一次,那么数组的元素必定是奇数个,二分之后需要比较中间数与左右两边是否出现,未出现则只出现一次,直接返回;往左查找还是往右查找还需要考虑两边数值的个数奇偶性,因为只出现一次的数只可能出现在个数为奇数的一边(去除掉与中间数相等的数后)

有序数组中的单一元素

O(n)写法:

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        i = 0
        while i < (n - 1):
            if nums[i] != nums[i + 1]:
                return nums[i]
            i += 2
        return nums[n - 1]

O(logn)写法:

class Solution:
    def singleNonDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        def get_once(arr, left, right):
            # 只剩一个元素直接返回
            if left == right:
                return arr[left]
            mid = (right + left) // 2
            L = right - mid
            if (arr[mid] != arr[mid - 1]) and (arr[mid] != arr[mid + 1]):
                return arr[mid]
            elif (L % 2):
                # 奇数个
                return get_once(arr, mid + 1, right) if (arr[mid] == arr[mid - 1]) else get_once(arr, left, mid - 1)
            else:
                # 偶数个
                return get_once(arr, left, mid - 2) if (arr[mid] == arr[mid - 1]) else get_once(arr, mid + 2, right)
        return get_once(nums, 0, n - 1)
0

评论区