※ 引述《Rushia (みけねこ的鼻屎)》之铭言：
: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array
: 1287. Element Appearing More Than 25% In Sorted Array
: 给你一个有序的数字阵列，找出该数字阵列出现次数超过元素数量25%的元素是哪个，
: 题目保证恰好一解。
虽然是easy不过看到题目突然想到一个解
保证恰好一个数字超过25%
所以答案必然是len*1/4 len*2/4 len*3/4其中一个
所以拿这三个值去各二分搜两次找上下界就可以得到区间
这样复杂度就是logn了
心情好还可以前面再做几个特判加速
然而题目length <= 10^4
搞一大串搞不好还比较慢
==
再多两个0不知道看不看得出差距
import bisect
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
l = len(arr)
q = l//4
if arr[0] == arr[q]:
return arr[0]
if arr[-1] == arr[-1-q]:
return arr[-1]
candidate = [arr[q], arr[l//2], arr[l*3//4]]
for i in range(2):
if candidate[i] == candidate[i+1]:
return candidate[i]
for c in candidate:
if bisect.bisect(arr, c) - bisect.bisect_left(arr, c) > q:
return c