1287. Element Appearing More Than 25% In Sorted Array

Problem

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.

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

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⁴
0 <= arr[i] <= 10⁵

Test Cases

1 2	class Solution: def findSpecialInteger(self, arr: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('arr, expected', [
    ([1,2,2,6,6,6,6,7,10], 6),
    ([1,1], 1),

    ([5], 5),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, arr, expected):
    assert sol.findSpecialInteger(arr) == expected

Thoughts

此题如果按照 easy 难度去做，应该直接遍历一遍 arr 吧。

先看一些特例：

如果 arr 的长度为 1，那么这唯一的元素即为所求。
如果 arr 的长度小于 8，那么所求的数字应该会出现超过一次，且不会有其他数字出现超过一次，可以遍历 arr，找到与前一个数字相等的数字，即为所求。

对于一般的情况，看 arr 的 25%、50% 和 75% 分位点，所求的数字一定是这三个数字中的某一个，只需要分别统计这三个数字的总次数，看超过 25% 的是谁。对于任意的 n，显然所求数字的最小次数为 n // 4 + 1。

对于指定的数字 num（num ∈ arr），可以用两次二分法找出 arr 中 num 的左右边界 [l, r)，其中 arr[l] 是第一个 num，arr[r] 是最后一个 num 右边的位置。用 Python 的 bisect_left 可以得到 l，bisect_right 可以得到 r，r - l 即为 num 的次数。

实际上不也可以不管前边提到的「特例」，直接看三个分位点数字的个数即可。

时间复杂度 O(log n)，空间复杂度 O(1)。

Code

solution.py

from bisect import bisect_left, bisect_right


class Solution:
    def findSpecialInteger(self, arr: list[int]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0]
        elif n < 8:
            prev = -1
            for num in arr:
                if num == prev:
                    return num
                prev = num

        edges = [n // 4, n // 2, 3 * n // 4]
        # if arr[edges[-1]] == arr[-1]:
        #     return arr[-1]

        min_count = n // 4 + 1
        bi_count = lambda num: bisect_right(arr, num) - bisect_left(arr, num)
        for edge in edges:
            if bi_count(arr[edge]) >= min_count:
                return arr[edge]

反向引用
- 2080. Range Frequency Queries

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。