Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1150.html
1150. Check If a Number Is Majority Element in a Sorted Array
Level
Easy
Description
Given an array nums
sorted in non-decreasing order, and a number target
, return True
if and only if target
is a majority element.
A majority element is an element that appears more than N/2
times in an array of length N
.
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.
Note:
1 <= nums.length <= 1000
1 <= nums[i] <= 10^9
1 <= target <= 10^9
Solution
Use binary search to find the leftmost index and the rightmost index of target
, and calculate how many times target
appears. If target
appears more than half of the array’s length, then return true
. Otherwise, return false
.
-
class Solution { public boolean isMajorityElement(int[] nums, int target) { int length = nums.length; int leftIndex = findLeft(nums, target); int rightIndex = findRight(nums, target); if (leftIndex < 0 && rightIndex < 0) return false; else { int majorityCount = rightIndex - leftIndex + 1; return majorityCount > length / 2; } } public int findLeft(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = nums[mid]; if (num == target) { if (mid - 1 >= low && nums[mid - 1] == target) high = mid - 1; else return mid; } else if (num < target) low = mid + 1; else high = mid - 1; } return -low - 1; } public int findRight(int[] nums, int target) { int low = 0, high = nums.length - 1; while (low <= high) { int mid = (high - low) / 2 + low; int num = nums[mid]; if (num == target) { if (mid + 1 <= high && nums[mid + 1] == target) low = mid + 1; else return mid; } else if (num < target) low = mid + 1; else high = mid - 1; } return -low - 1; } }
-
// OJ: https://leetcode.com/problems/check-if-a-number-is-majority-element-in-a-sorted-array/ // Time: O(logN) // Space: O(1) class Solution { public: bool isMajorityElement(vector<int>& A, int target) { return upper_bound(begin(A), end(A), target) - lower_bound(begin(A), end(A), target) > A.size() / 2; } };
-
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
-
func isMajorityElement(nums []int, target int) bool { n := len(nums) left := sort.Search(n, func(i int) bool { return nums[i] >= target }) right := sort.Search(n, func(i int) bool { return nums[i] > target }) return right-left > n/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; }