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

🟢   🔖  数组  🔗 力扣 LeetCode

题目

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.

Example 1:

Input: arr = [1,2,2,6,6,6,6,7,10]

Output: 6

Example 2:

Input: arr = [1,1]

Output: 1

Constraints:

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

题目大意

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

请你找到并返回这个整数

示例：

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

输出： 6

提示：

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

解题思路

可以使用双指针来解决这道题。

1. 计算目标数字出现的最小次数为 target = Math.floor(n / 4) + 1。
2. 使用两个指针 left 和 i，分别指向当前数字的起始位置和遍历位置；
3. 遍历数组，若当前元素 arr[i] 不等于 arr[left]，检查 [left, i) 之间的元素数量是否超过目标值 target；
   • 如果满足条件，可以提前终止循环，直接返回 arr[left]；
   • 如果不满足，将 left 更新为当前元素的位置。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次。
• 空间复杂度：O(1)，只使用了常量级变量。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function (arr) {
	const n = arr.length;
	const target = Math.floor(n / 4) + 1;
	let left = 0;

	for (let i = 0; i < n; i++) {
		if (arr[i] !== arr[left]) {
			// 检查区间长度
			if (i - left >= target) {
				break;
			}
			left = i; // 更新左指针
		}
	}
	return arr[left];
};