Easy

题目描述

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

示例 1：

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

示例 2：

输入：arr = [1,1]
输出：1

提示：

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

思路提示：

  • 将数组分成四部分 [1-25%] [25-50%] [50-75%] [75%-100%]
  • 答案应该在某个区间的端点处
  • 可以用二分查找来检查某个元素的出现频率

解题思路

解题思路

这道题有几种解法：

方法一：直接遍历统计（简单）

最直观的方法是遍历数组统计每个元素的出现次数，当某个元素的出现次数超过 n/4 时返回该元素。

方法二：候选点检查（推荐）

根据题目提示，我们可以利用数组有序的特性。如果一个元素出现次数超过25%，那么它必然会出现在以下位置之一：

  • arr[n/4]：第一个四分位点
  • arr[n/2]：中位数
  • arr[3*n/4]：第三个四分位点

我们只需要检查这三个候选位置的元素，然后用二分查找计算它们的出现次数即可。

方法三：滑动窗口

由于数组有序，我们可以用滑动窗口的思想。如果某个元素出现次数超过25%，那么在长度为 n/4 + 1 的窗口中，首尾元素必然相等。

这里我们采用候选点检查的方法，因为它既高效又易于实现。

代码实现

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int threshold = n / 4;
        
        // 候选位置：1/4, 1/2, 3/4 处的元素
        vector<int> candidates = {arr[n/4], arr[n/2], arr[3*n/4]};
        
        for (int candidate : candidates) {
            // 使用二分查找找到第一个和最后一个出现位置
            int left = lower_bound(arr.begin(), arr.end(), candidate) - arr.begin();
            int right = upper_bound(arr.begin(), arr.end(), candidate) - arr.begin();
            
            if (right - left > threshold) {
                return candidate;
            }
        }
        
        return -1; // 理论上不会到这里
    }
};

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        threshold = n // 4
        
        # 候选位置：1/4, 1/2, 3/4 处的元素
        candidates = [arr[n//4], arr[n//2], arr[3*n//4]]
        
        for candidate in candidates:
            # 使用二分查找找到第一个和最后一个出现位置
            left = bisect.bisect_left(arr, candidate)
            right = bisect.bisect_right(arr, candidate)
            
            if right - left > threshold:
                return candidate
        
        return -1  # 理论上不会到这里

public class Solution {
    public int FindSpecialInteger(int[] arr) {
        int n = arr.Length;
        int threshold = n / 4;
        
        // 候选位置：1/4, 1/2, 3/4 处的元素
        int[] candidates = {arr[n/4], arr[n/2], arr[3*n/4]};
        
        foreach (int candidate in candidates) {
            // 使用二分查找找到第一个和最后一个出现位置
            int left = Array.BinarySearch(arr, candidate);
            if (left < 0) left = ~left;
            else {
                // 找到第一个出现位置
                while (left > 0 && arr[left - 1] == candidate) left--;
            }
            
            int right = left;
            while (right < n && arr[right] == candidate) right++;
            
            if (right - left > threshold) {
                return candidate;
            }
        }
        
        return -1; // 理论上不会到这里
    }
}

/**
 * @param {number[]} arr
 * @return {number}
 */
var findSpecialInteger = function(arr) {
    const n = arr.length;
    const threshold = Math.floor(n / 4);
    
    // 候选位置：1/4, 1/2, 3/4 处的元素
    const candidates = [arr[Math.floor(n/4)], arr[Math.floor(n/2)], arr[Math.floor(3*n/4)]];
    
    for (const candidate of candidates) {
        // 找到第一个出现位置
        let left = 0;
        while (left < n && arr[left] < candidate) left++;
        
        // 找到最后一个出现位置
        let right = left;
        while (right < n && arr[right]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
候选点检查O(log n)O(1)
直接遍历O(n)O(1)
滑动窗口O(n)O(1)

推荐使用候选点检查方法，时间复杂度最优。