标签: 数组
难度: Easy
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6
提示：
1 <= arr.length <= 10^40 <= arr[i] <= 10^5
Submission
运行时间: 24 ms
内存: 17.2 MB
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
c = n // 4
for i in range(n-c):
if arr[i] == arr[i+c]:
return arr[i]
return -1
Explain
这个题解利用了数组的有序性和问题的条件（一个元素出现次数超过25%）。计算出n/4的整数值存入变量c，这代表数组长度的四分之一。如果一个元素的出现次数超过25%，那么在数组中这个元素至少会出现在连续的c+1个位置上。因此，算法遍历数组，对于每个位置i，检查位置i和位置i+c上的元素是否相同。如果相同，说明从位置i开始的元素至少出现c+1次，满足题目要求，直接返回该元素。如果遍历结束都没有找到满足条件的元素，则返回-1。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr) # 获取数组长度
c = n // 4 # 计算四分之一的长度
for i in range(n-c): # 遍历数组，直至最后一个可以检查的位置
if arr[i] == arr[i+c]: # 检查当前位置和后面c个位置的元素是否相同
return arr[i] # 如果相同，返回该元素
return -1 # 如果没有找到符合条件的元素，返回-1
Explore
通过遍历到数组倒数第c个元素（即遍历到索引n-c）来确保每个可能的起始位置i都与其后c个位置的元素进行比较。这种遍历方式确保即使是数组末尾的元素，也会被考察是否与前面的元素相同，从而检查是否满足出现次数超过25%的条件。
选择检查`arr[i] == arr[i+c]`是因为这是一种高效的方法来确认一个元素是否至少占据了连续的c+1个位置，这是符合超过25%出现次数的必要条件。如果数组是有序的，且某元素出现超过25%，那么这个元素必然会在某个位置i开始，连续出现至少c+1次。存在其他方法，如使用哈希表统计每个元素的频率，或使用摩尔投票算法，但这些方法可能不如直接利用数组有序性来的简单和高效。
如果数组长度较短或c的值相对较大，这可能导致循环的迭代次数减少，因为n-c的值会变小。在极端情况下，如果数组长度n小于或等于c，那么n-c将为0或负数，这意味着循环可能完全不执行，算法将直接返回-1。这种情况下，算法可能无法正确地检测到确实存在的超过25%的元素，尤其是在只有一个或两个元素的情况下。
当数组中的元素非常集中，即大部分元素是同一个数字时，这种解法效率非常高。因为在这种情况下，大多数的比较`arr[i] == arr[i+c]`将迅速返回true，使得算法可以在第一次遇到满足条件的元素时立即结束循环并返回结果。这种情况下算法的时间复杂度接近于O(1)，因为它可能只需要进行一次比较。