地址
目描述
给你一个非递减的 有序 整数数组, 已知这个数组中恰好有一个整数, 它的出现次数超过数组元素总数的 25%.
请你找到并返回这个整数
示例:
输入: arr = [1,2,2,6,6,6,6,7,10]
输出: 6
提示:
- 1 <= arr.length <= 10^4
- 0 <= arr[i] <= 10^5
算法 1
已经排序 而且超过 25%
那么可以直接比较 25% 的长度间隔的两个数是否相等
C++ 代码
- class Solution {
- public:
- int findSpecialInteger(vector& arr) {
- int n = arr.size(); int len = n/4;
- for(int i = 0; i < n;i++){
- if(i+len < n && arr[i] == arr[i+len]){
- return arr[i];
- }
- }
- return -1;
- }
- };
来源: http://www.bubuko.com/infodetail-3331973.html