Question

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

解法

方法一：二分查找

我们注意到，数组 $nums$ 中的元素是非递减的，也就是说，数组 $nums$ 中的元素单调递增。因此，我们可以使用二分查找的方法，找到数组 $nums$ 中第一个大于等于 $target$ 的元素的下标 $left$，以及第一个大于 $target$ 的元素的下标 $right$。如果 $right - left > \frac{n}{2}$，则说明数组 $nums$ 中的元素 $target$ 出现的次数超过了数组长度的一半，因此返回 $true$，否则返回 $false$。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

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

class Solution {
  public boolean isMajorityElement(int[] nums, int target) {
    int left = search(nums, target);
    int right = search(nums, target + 1);
    return right - left > nums.length / 2;
  }

  private int search(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  bool isMajorityElement(vector<int>& nums, int target) {
    auto left = lower_bound(nums.begin(), nums.end(), target);
    auto right = upper_bound(nums.begin(), nums.end(), target);
    return right - left > nums.size() / 2;
  }
};

func isMajorityElement(nums []int, target int) bool {
  left := sort.SearchInts(nums, target)
  right := sort.SearchInts(nums, target+1)
  return right-left > len(nums)/2
}

function isMajorityElement(nums: number[], target: number): boolean {
  const search = (x: number) => {
    let left = 0;
    let right = nums.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
  const left = search(target);
  const right = search(target + 1);
  return right - left > nums.length >> 1;
}

方法二：二分查找（优化）

方法一中，我们使用了两次二分查找，分别找到数组 $nums$ 中第一个大于等于 $target$ 的元素的下标 $left$，以及第一个大于 $target$ 的元素的下标 $right$。但是，我们可以使用一次二分查找，找到数组 $nums$ 中第一个大于等于 $target$ 的元素的下标 $left$，然后判断 $nums[left + \frac{n}{2}]$ 是否等于 $target$，如果相等，说明数组 $nums$ 中的元素 $target$ 出现的次数超过了数组长度的一半，因此返回 $true$，否则返回 $false$。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $nums$ 的长度。

class Solution:
  def isMajorityElement(self, nums: List[int], target: int) -> bool:
    left = bisect_left(nums, target)
    right = left + len(nums) // 2
    return right < len(nums) and nums[right] == target

class Solution {
  public boolean isMajorityElement(int[] nums, int target) {
    int n = nums.length;
    int left = search(nums, target);
    int right = left + n / 2;
    return right < n && nums[right] == target;
  }

  private int search(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  bool isMajorityElement(vector<int>& nums, int target) {
    int n = nums.size();
    int left = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    int right = left + n / 2;
    return right < n && nums[right] == target;
  }
};

func isMajorityElement(nums []int, target int) bool {
  n := len(nums)
  left := sort.SearchInts(nums, target)
  right := left + n/2
  return right < n && nums[right] == target
}

function isMajorityElement(nums: number[], target: number): boolean {
  const search = (x: number) => {
    let left = 0;
    let right = n;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
  const n = nums.length;
  const left = search(target);
  const right = left + (n >> 1);
  return right < n && nums[right] === target;
}