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 <= 10001 <= nums[i], target <= 109nums is sorted in non-decreasing order.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.
Java
C++
Go
TypeScript
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.
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Binary Search | — |
| Binary Search (Optimized) | — |
Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimal • take U forward • 437,699 views views
Watch 9 more video solutions →Practice Check If a Number Is Majority Element in a Sorted Array with our built-in code editor and test cases.
Practice on FleetCode