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
个人解法
遍历前75%的数，比较arr[i]是否与1/4长度n后的arr[j]相等
题目说“恰好有一个符合的数”，所以当长度n < 4的时候，全部数字肯定是一样的，不然答案数量会大于1，与题目描述不符。直接返回arr[0]。
遍历数组里前75%的数，因为是排序数组，相同的数一定排在一起，所以对于每一个数a[i]，只需与n的25%长度后的对应数值a[j]比较，其中j = i + n // 4。
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
if n < 4:
return arr[0]
for i in range(n // 4 * 3 + 1):
if arr[i] == arr[i + n // 4]:
return arr[i]
