LeetCode 题解工作台
有序数组中出现次数超过25%的元素
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。 请你找到并返回这个整数 示例： 输入： arr = [1,2,2,6,6,6,6,7,10] 输出： 6 提示： 1 0
1
题型
7
代码语言
3
相关题
当前训练重点
简单 · 数组·driven
答案摘要
我们从头开始遍历数组 ，对于每个元素 ，我们检查 是否等于 $\textit{arr}[i + \left\lfloor \frac{n}{4} \right\rfloor]$，其中 是数组的长度。如果等于，那么 就是我们要找的元素，直接返回即可。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·driven 题型思路
题目描述
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6
提示：
1 <= arr.length <= 10^40 <= arr[i] <= 10^5
解题思路
方法一：遍历
我们从头开始遍历数组 ，对于每个元素 ，我们检查 是否等于 ，其中 是数组的长度。如果等于，那么 就是我们要找的元素，直接返回即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
for i, x in enumerate(arr):
if x == arr[(i + (n >> 2))]:
return x
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) because we only check a constant number of quarter positions rather than the whole array. Space complexity is O(1) as no extra data structures are used beyond index variables. |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Candidates at quarter indices often reveal the element exceeding 25% frequency.
- question_mark
Sorting guarantees that any valid element will span multiple quarter boundaries.
- question_mark
Linear scans across all indices are unnecessary and may indicate inefficiency.
常见陷阱
外企场景- error
Failing to use sorted property and checking all elements linearly instead of quarter indices.
- error
Miscounting occurrences when the repeating element is near segment boundaries.
- error
Assuming multiple elements could exceed 25% instead of leveraging the problem's unique element guarantee.
进阶变体
外企场景- arrow_right_alt
Find an element appearing more than 33% in a sorted array, adjusting index checks accordingly.
- arrow_right_alt
Handle arrays where multiple elements appear frequently but only one exceeds 25%, ensuring correctness.
- arrow_right_alt
Apply similar quarter-based search for strings in a sorted list to find the dominant string.