LeetCode1287.有序数组中出现次数超过25%的元素：遍历

【LetMeFly】1287.有序数组中出现次数超过25%的元素：遍历

力扣题目链接： leetcode /problems/element-appearing-more-than-25-in-sorted-array/

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

请你找到并返回这个整数

 

示例：

输入：arr = [1,2,2,6,6,6,6,7,10] 输出：6

 

提示：

1 <= arr.length <= 10^40 <= arr[i] <= 10^5 解题方法：遍历

对于长度为 n n n的有序数组，对于一个首次出现下标为 i i i的数：

整个数出现次数超过了 25 % 25\% 25% 等价于 下标 ⌊ n 4 ⌋ + i \lfloor\frac{n}{4}\rfloor+i ⌊4n​⌋+i仍为这个数。

时间复杂度 O ( l e n ( a r r ) ) O(len(arr)) O(len(arr))空间复杂度 O ( 1 ) O(1) O(1) AC代码 C++ /* * @Author: LetMeFly * @Date: 2025-02-17 14:38:51 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-17 14:42:26 */ class Solution { public: int findSpecialInteger(vector<int>& arr) { int locDiff = arr.size() / 4; for (int i = 0; 1; i++) { if (arr[i] == arr[i + locDiff]) { return arr[i]; } } } }; Python ''' Author: LetMeFly Date: 2025-02-17 14:38:57 LastEditors: LetMeFly.xyz LastEditTime: 2025-02-17 14:43:22 ''' from typing import List class Solution: def findSpecialInteger(self, arr: List[int]) -> int: locDiff = len(arr) // 4 for i in range(len(arr)): if arr[i] == arr[i + locDiff]: return arr[i] return -1 # Fake Return Java /* * @Author: LetMeFly * @Date: 2025-02-17 14:39:05 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-17 14:44:38 */ class Solution { public int findSpecialInteger(int[] arr) { int locDiff = arr.length / 4; for (int i = 0; true; i++) { if (arr[i] == arr[i + locDiff]) { return arr[i]; } } } } Go /* * @Author: LetMeFly * @Date: 2025-02-17 14:39:01 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-17 14:47:00 */ package main func findSpecialInteger(arr []int) int { locDiff := len(arr) / 4 for i := 0; true; i++ { if arr[i] == arr[i + locDiff] { return arr[i] } } return -1 // Fake Return - 及时上面是for true也需要return }

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

Tisfy： blog.letmefly.xyz/2025/02/17/LeetCode 1287.有序数组中出现次数超过25的元素