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

难度：简单

题目

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

请你找到并返回这个整数

示例：

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

输出：6

提示：

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

Reference

题解

已知该整数出现次数超过元素总数的25%，则该元素必然是25%、50%、75%分位数中的至少一个。对于这三个分位数，使用二分查找寻找它出现的第一个位置和最后一个位置，判断出现次数是否超过25%即可。

import bisect

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        length = len(arr)
        # Results are here
        possibleResults = [
            arr[int((len(arr) - 1) * (i / 4))]
            for i in range(5)
        ]
        maxNum, maxCount = 0, 0
        for num in possibleResults:
            newCount = bisect.bisect_right(arr, num) - bisect.bisect_left(arr, num)
            if newCount > maxCount:
                maxCount = newCount
                maxNum = num
        return maxNum

评论