面试算法题：判断有序数组中是否存在出现次数超n/4的元素

面试问题 #

给定一个包含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

疑问 #

请问这个滑动窗口解法是否符合面试官的意图？另外是否存在更优的低于线性复杂度的解法？

内容的提问来源于stack exchange，提问作者Nab