Solutions CS101

Appearance

1287.有序数组中出现次数超过25%的元素 ​

https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array/

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

请你找到并返回这个整数。

示例：

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

提示：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5
python
class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0]
        
        threshold = n / 4
        cur, cnt, eps = arr[0], 1, 1e-7
        for fast in arr[1:]:
            if fast == cur:
                cnt += 1
                if cnt - threshold > eps:
                    return fast
            else:
                cur, cnt = fast, 1
python
from typing import List

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        # 计算阈值（数组长度的1/4）
        threshold = len(arr) / 4
        
        # 遍历数组，检查每个元素与其后第threshold个元素是否相同
        for i in range(len(arr)):
            if arr[i] == arr[i + int(threshold)]:
                return arr[i]
        
        # 如果没有找到（理论上不会到达这里，因为题目保证了存在这样的元素）
        return -1