题目
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6提示：
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5解答
# class Solution:
# def findSpecialInteger(self, arr):
# d = {}
# length = len(arr)
# fo = length // 4 + 1
# for x in arr:
# if x in d:
# d[x] += 1
# if d[x] >= fo:
# return x
# else:
# d[x] = 1
# return x
# 不用额外空间
class Solution:
def findSpecialInteger(self, arr):
if len(arr) == 1:
return arr[0]
length = len(arr)
result, cnt = arr[0], 1
for x in range(1, length):
if arr[x] == result:
cnt += 1
if cnt*4 > length:
return result
else:
result = arr[x]
cnt = 1
s = Solution()
ans = s.findSpecialInteger([1, 2, 2, 6, 6, 6, 6, 7, 10])
print(ans)
# 6