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

Categories:

题目描述
思路分析
1. 解法一：采样 + 二分统计（推荐）
相似题目

题目描述

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

思路分析

解法一：采样 + 二分统计（推荐）

核心思路：

有序数组中出现次数超过 25% 的元素必定出现在索引 n/4、n/2 或 3n/4 位置。

取这几个位置的值为候选，二分统计其出现次数即可。

复杂度分析：

时间复杂度：O(log n)，最多统计 3 次。

空间复杂度：O(1)。

class Solution {
    public int findSpecialInteger(int[] arr) {
        int n = arr.length;
        int[] idxs = {n / 4, n / 2, 3 * n / 4};
        for (int idx : idxs) {
            int val = arr[idx];
            int left = lowerBound(arr, val);
            int right = upperBound(arr, val);
            if (right - left > n / 4) {
                return val;
            }
        }
        return -1;
    }

    private int lowerBound(int[] arr, int target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }

    private int upperBound(int[] arr, int target) {
        int l = 0;
        int r = arr.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (arr[m] > target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

import "sort"

func findSpecialInteger(arr []int) int {
    n := len(arr)
    idxs := []int{n / 4, n / 2, 3 * n / 4}
    for _, idx := range idxs {
        val := arr[idx]
        left := sort.SearchInts(arr, val)
        right := sort.Search(len(arr), func(i int) bool {
            return arr[i] > val
        })
        if right-left > n/4 {
            return val
        }
    }
    return -1
}

相似题目

题目	难度	考察点
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找
278. 第一个错误的版本	简单	二分查找
704. 二分查找	简单	二分查找
162. 寻找峰值	中等	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/61576801