【每日一题】Leetcode 1287. 有序数组中出现次数超过25%的元素

【每日一题】Leetcode 1287. 有序数组中出现次数超过25%的元素

——跳转原题

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

提示：

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

隐藏信息：1. 有且仅有一个答案；2. 必有一个答案

思路 1：（遍历，时间复杂度\(O(n)\)）

1. 从左至右遍历数组，记录元素出现次数，当次数大于长度的 25% 后直接返回当前元素
2. 由于是有序列表，所以当当前元素变化时，直接更新元素出现次数和当前元素。

代码 1：（遍历，时间复杂度\(O(n)\)）

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        threshold = len(arr)
        cur = None
        cur_count = 0
        for item in arr:
            if item != cur:
                if cur_count * 4 > threshold: # 不使用 threshold * 0.25 是为了保证不被浮点精度影响
                    return cur
                cur_count = 0
                cur = item
            cur_count += 1
        return cur

思路 2：（二分查找，时间复杂度\(O(log(n))\)）

1. 数学归纳法：设满足要求的答案为 x，数组为 arr
   ① 当 x 至少出现 span = 1 次时，其必定在 [arr[0], arr[1], arr[2], ... arr[span i], arr[span (i + 1)]]中
   ② 当 x 至少出现 2 次时，其必定在 [arr[0], arr[2], arr[4], ..., arr[span i], arr[span (i + 1)]]
   ...
   ③ 当 x 至少出现 span = len(arr) // 4 + 1 次时，其必定在 [arr[0], arr[span], arr[span 2], ..., arr[span i], arr[span * (i + 1)]
2. 所以根据 1 中得到的数组进行查找，并判断查找到的元素的位置区间。
3. python 中可以使用 bisect 模块中的 bisect.bisect_left 和 bisect.bisect_right 分别查找元素的左侧位置和右侧位置

知识点：bisect 可用于有序序列的插入和非逆序系列的二分查找

代码 2：（二分查找，时间复杂度\(O(log(n))\)）

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        span = n // 4 + 1
        for i in range(0, n, span):
            iter_l = bisect.bisect_left(arr, arr[i])
            iter_r = bisect.bisect_right(arr, arr[i])
            if iter_r - iter_l >= span:
                return arr[i]
        return -1

感谢浏览，欢迎关注祁彧w博客！