日期: 2025 年 2 月 17 日

目标

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

请你找到并返回这个整数

示例：

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

说明：

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

思路

有一个非递减有序整数数组，数组中恰好有一个整数出现次数大于元素总数的 25%，返回这个整数。

检查长度为 n / 4 + 1 的窗口首尾元素是否相等即可。

代码

/**
 * @date 2025-02-17 8:41
 */
public class FindSpecialInteger1287 {

    public int findSpecialInteger_v1(int[] arr) {
        int n = arr.length;
        int left = 0, right = n / 4;
        while (right < n) {
            if (arr[right] == arr[left]) {
                return arr[left];
            }
            left++;
            right++;
        }
        return -1;
    }

}

性能