Leetcode1287：有序数组中出现次数超过25%的元素

题目描述：

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

请你找到并返回这个整数。

代码思路： 初始化变量： n = len(arr)：计算数组 arr 的长度。diff = n // 4：计算一个间隔，这个间隔是数组长度的四分之一（向下取整）。由于我们要找的整数出现次数超过数组长度的 25%，所以这个间隔内的某个位置（或多个位置）很可能包含这个特殊整数。 遍历数组： 使用 for i in range(n - diff) 遍历数组，直到倒数第 diff 个元素。这是因为我们要比较当前元素 arr[i] 和它后面 diff 个位置的元素 arr[i + diff]。 检查并返回结果： 在循环中，使用 if arr[i] == arr[i + diff] 检查当前元素和后面间隔 diff 个位置的元素是否相等。如果相等，说明找到了一个可能的特殊整数。由于数组是非递减有序的，且这个整数出现次数超过数组长度的 25%，那么在间隔 diff 内（或更长的范围内），这个整数会连续出现多次。因此，一旦找到这样的相等元素对，就可以直接返回 arr[i]，因为它就是我们要找的特殊整数。

为什么这个方法有效：

由于数组是非递减有序的，所以相同的元素会连续出现。特殊整数的出现次数超过数组长度的 25%，即至少 n // 4 次（向下取整）。通过检查间隔 n // 4 的元素对，我们确保至少能够捕捉到特殊整数的一个连续出现区间。一旦找到这样的连续出现区间（即两个元素相等），由于数组的有序性，我们可以确信这个整数就是特殊整数。 代码实现： class Solution: def findSpecialInteger(self, arr: List[int]) -> int: n = len(arr) diff = n // 4 for i in range(n - diff): if arr[i] == arr[i + diff]: return arr[i]