[LeetCode] 每日一题 1287. 有序数组中出现次数超过25%的元素

题目链接

https://leetcode.cn/problems/element-appearing-more-than-25-in-sorted-array

题目描述

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 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 的连续区间，区间内所有值相同

基于这个特性，我们可以用两个指针 left 和 right 来维护一个滑动窗口，窗口的长度固定为 n / 4。left 代表当前区间的起点，right 代表区间的终点。如果 arr[left] == arr[right]，说明 arr[left] 在该区间内连续出现，且数量超过 25%，直接返回 arr[left]。否则，我们右移窗口，继续检查下一个区间，直到找到满足条件的元素

代码实现

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

复杂度分析

• 时间复杂度：O(n)，因为 left 和 right 指针线性遍历数组，每个元素最多访问一次

• 空间复杂度：O(1)，我们只使用了两个额外的变量 left 和 right，不占用额外空间

总结

这道题的核心在于利用有序数组的特性，避免了额外的计数操作，而是通过滑动窗口的方式，直接找到满足条件的元素。相较于暴力遍历计数的方法，这种方式更加高效，逻辑也更加清晰

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。