Question

1150. Check If a Number Is Majority Element in a Sorted Array

中文文档

Description

Given an integer array nums sorted in non-decreasing order and an integer target, return true _if_ target _is a majority element, or _false_ otherwise_.

A majority element in an array nums is an element that appears more than nums.length / 2 times in the array.

 

Example 1:

Input: nums = [2,4,5,5,5,5,5,6,6], target = 5
Output: true
Explanation: The value 5 appears 5 times and the length of the array is 9.
Thus, 5 is a majority element because 5 > 9/2 is true.

Example 2:

Input: nums = [10,100,101,101], target = 101
Output: false
Explanation: The value 101 appears 2 times and the length of the array is 4.
Thus, 101 is not a majority element because 2 > 4/2 is false.

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i], target <= 109
• nums is sorted in non-decreasing order.

Solutions

Solution 1: Binary Search

We notice that the elements in the array $nums$ are non-decreasing, that is, the elements in the array $nums$ are monotonically increasing. Therefore, we can use the method of binary search to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and the index $right$ of the first element in the array $nums$ that is greater than $target$. If $right - left > \frac{n}{2}$, it means that the number of occurrences of the element $target$ in the array $nums$ exceeds half of the length of the array, so return $true$, otherwise return $false$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $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;
}

Solution 2: Binary Search (Optimized)

In Solution 1, we used binary search twice to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and the index $right$ of the first element in the array $nums$ that is greater than $target$. However, we can use binary search once to find the index $left$ of the first element in the array $nums$ that is greater than or equal to $target$, and then judge whether $nums[left + \frac{n}{2}]$ is equal to $target$. If they are equal, it means that the number of occurrences of the element $target$ in the array $nums$ exceeds half of the length of the array, so return $true$, otherwise return $false$.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $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;
}