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

题目

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

请你找到并返回这个整数

示例

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

提示

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

算法

map

其实这里维护一个数字变量count用来存储当前遍历数字的出现次数即可，如果遍历数字发生改变则重置count，如果count超过arr.length * 0.25则直接返回这个数字

export const findSpecialInteger = (arr) => {
	const map = new Map();
	for (let i = 0; i < arr.length; i++) {
		if (map.has(arr[i])) {
			map.set(arr[i], map.get(arr[i]) + 1);
		} else {
			map.set(arr[i], 1);
		}
		if (map.get(arr[i]) > arr.length * 0.25) return arr[i];
	}
	return -1;
};

双指针

既然数字出现次数超过25%，那么必然有arr[i]和arr[i + ~~(arr.length * 0.25)]相同

export const findSpecialInteger = (arr) => {
	let slow = 0,
		fast = ~~(arr.length * 0.25);
	while (fast < arr.length) {
		if (arr[slow] === arr[fast]) return arr[slow];
		slow++;
		fast++;
	}
	return -1;
};