当前位置：首页 > article >正文

力扣LeetCode: 1287 有序数组中出现次数超过25%的元素

article 2025/2/23 7:19:21

题目：

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

请你找到并返回这个整数

示例：

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

提示：

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

解法：数组遍历

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int target = n / 4;
        int count = 1;
        
        for (int i = 1; i < n; ++i) {
            if (arr[i] == arr[i - 1]) {
                ++count;
                if (count > target) {
                    return arr[i];
                }
            } else {
                count = 1;
            }
        }
        
        // 如果数组只有一个元素，直接返回该元素
        return arr[0];
    }
};

代码解释：

n 是数组的长度，target 是25%的长度。
count 用于统计当前元素的出现次数，初始值为1。
遍历数组，从第二个元素开始：
- 如果当前元素与前一个元素相同，则增加 count。
- 如果 count 超过了 target，则返回当前元素。
- 如果当前元素与前一个元素不同，则重置 count 为1。
如果数组只有一个元素，直接返回该元素。