说在前面
🎈今天给大家带来的是算法练习,题目为"有序数组中出现次数超过25%的元素"。
题目描述
给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。\
请你找到并返回这个整数。\
示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6提示：
1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5思路分析
题目要求我们找出在有序数组中出现次数超过数组元素总数的25%的哪一个元素，这里有一个非常重要的前提条件，就是给出的数组是一个非递减的有序整数数组，所以也就是说数值相等的元素在数组中的位置是连在一起的，所以我们可以先根据数组长度来得出数组25%的数目是多少，然后遍历判断元素与后25%位置的元素是否相等，相等的话该元素即是答案，具体步骤如下：
- 计算数组的25%数目
计算数目的时候我们向下取整就可以了，以为我们后面进行比较的是i和i+len，两元素的距离是len，也就是说这段区间中总共有len + 1个元素，len + 1就已经超过原数组长度的25%了。
let len = Math.floor(arr.length / 4);- 遍历判断元素与后25%位置的元素是否相等
for(let i = 0; i < arr.length - len - 1; i++){
if(arr[i] == arr[len + i]) return arr[i];
}AC代码
/**
* @param {number[]} arr
* @return {number}
*/
var findSpecialInteger = function(arr) {
let len = Math.floor(arr.length / 4);
for(let i = 0; i < arr.length - len - 1; i++){
if(arr[i] == arr[len + i]) return arr[i];
}
return arr[arr.length - 1];
};说在后面
🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
