查找有序数组中是否有任何数字出现超过 n/4 次

Question

我在面试中被问到以下问题：

给定一个包含 n 个数字的排序数组（其中 n 是 4 的倍数），返回是否有任何数字出现超过 n/4 次。

我最初的想法是迭代数组并保留一个计数器：

limit = len(nums) // 4
counter = 1

for i in range(1, len(nums)):
    if nums[i] == nums[i-1]:
        counter += 1

        if counter > limit:
            return True
    else:
        counter = 1

return False

但是面试官问我是否可以做得更好。排序数组，比线性复杂度更好，我立即想到“二分查找”...我探索了这条路径，但毫无头绪。

几分钟后，他给出了提示：“如果存在 i，其中 nums[i] == nums[i + len(nums) / 4]”，是否意味着我们应该返回 true？

我试图将其应用到我的二分搜索中，但没有直接思考，所以提示超出了我的头脑......回想起来，这是微不足道的，但我只看到如何通过滑动窗口应用它：

limit = len(nums) // 4

for i in range(limit, len(nums)):
    if nums[i] == nums[i-limit]:
        return True

return False

是面试官的意思吗？或者有更好的非线性解决方案吗？

Answer 1

在

nums

中出现超过n/4次的数字一定是

nums[::len(nums)//4]

的元素之一。对于每个这样的数字，我们对它出现的第一个位置执行二分搜索，并检查相同的数字是否出现在

len(nums)//4

点之后：

import bisect
def check(nums):
    n = len(nums)
    assert n % 4 == 0

    for i in nums[::n//4]):
        first_appearance = bisect.bisect_left(nums, i)
        if first_appearance + n//4 < len(nums) and nums[first_appearance + n//4] == i:
            return True
    return False

我们最多执行 4 次二分查找，最多执行恒定数量的其他工作，因此时间复杂度为 O(log n)。