1287. 有序数组中出现次数超过25%的元素

文章目录

• 一、题干与思路
• • 题干
  • 思路
• 二、代码实现

---

一、题干与思路 题干

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

首先我们看到，数组的值和长度都比较大，就要慎重考虑使用hash数组去计算每个元素的个数了，所以这里我们使用了一个巧妙的办法，就是先对数组进行排序，然后用一个整形变量去计算每个连续相同值的个数，乘以4大于等于长度就返回这个值。

二、代码实现

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int num=0;
        sort(arr.begin(), arr.end());
        for (int i = 1;i < arr.size();i++) {
            if (arr[i-1] == arr[i]) {
                num++;//计算连续相等值的个数
                if (num*4 > arr.size()) {
                    return arr[i];
                }
            } else {
                num = 1;//如果遇到不相等的了，就直接重新设置为1，然后进入下一个值的计数
            }
        }
        return arr[0];
    }
};