README.md

1150. 检查一个数是否在数组中占绝大多数

English Version

题目描述

给出一个按 非递减 顺序排列的数组 nums，和一个目标数值 target。假如数组 nums 中绝大多数元素的数值都等于 target，则返回 True，否则请返回 False。

所谓占绝大多数，是指在长度为 N 的数组中出现必须 超过 N/2 次。

 

示例 1：

输入：nums = [2,4,5,5,5,5,5,6,6], target = 5
输出：true
解释：
数字 5 出现了 5 次，而数组的长度为 9。
所以，5 在数组中占绝大多数，因为 5 次 > 9/2。

示例 2：

输入：nums = [10,100,101,101], target = 101
输出：false
解释：
数字 101 出现了 2 次，而数组的长度是 4。
所以，101 不是 数组占绝大多数的元素，因为 2 次 = 4/2。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9
• 1 <= target <= 10^9

解法

“二分查找”求 target 在数组 nums 中的左右边界。

Python3

自己实现二分查找：

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        def bsearch_left(nums, target, left, right):
            while left < right:
                mid = (left + right) >> 1
                if nums[mid] >= target:
                    right = mid
                else:
                    left = mid + 1
            return left if nums[left] == target else -1

        def bsearch_right(nums, target, left, right):
            while left < right:
                mid = (left + right + 1) >> 1
                if nums[mid] <= target:
                    left = mid
                else:
                    right = mid - 1
            return left if nums[left] == target else -1

        n = len(nums)
        left = bsearch_left(nums, target, 0, n - 1)
        if left == -1:
            return False
        right = bsearch_right(nums, target, left, n - 1)
        if right == -1:
            return False
        return right - left + 1 > n >> 1

使用 bisect 实现二分查找：

class Solution:
    def isMajorityElement(self, nums: List[int], target: int) -> bool:
        left, right = bisect.bisect_left(nums, target), bisect.bisect_right(nums, target)
        return right - left > (len(nums) >> 1)

Java

class Solution {
    public boolean isMajorityElement(int[] nums, int target) {
        int n = nums.length;
        int left = bsearchLeft(nums, target, 0, n - 1);
        if (left == -1) {
            return false;
        }
        int right = bsearchRight(nums, target, left, n - 1);
        if (right == -1) {
            return false;
        }
        return right - left + 1 > (n >> 1);
    }

    private int bsearchLeft(int[] nums, int target, int left, int right) {
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[left] == target ? left : -1;
    }

    private int bsearchRight(int[] nums, int target, int left, int right) {
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return nums[left] == target ? left : -1;
    }
}

...