1150. Check If a Number Is Majority Element in a Sorted Array π
SourceBiweekly Contest 6 Q1DifficultyEasyRating1249
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 <= 10001 <= nums[i], target <= 109numsis sorted in non-decreasing order.
Solutions
Solution 1: Binary Search
Thinking
In a sorted array the count of \(\textit{target}\) is the gap between its left and right bounds. Two binary searches find the first \(\ge \textit{target}\) and the first \(>\textit{target}\); the gap exceeds \(n/2\) iff \(\textit{target}\) is a majority. A linear count is unnecessary for large \(n\).
We notice that the elements in the array \(\textit{nums}\) are non-decreasing, that is, the elements in the array \(\textit{nums}\) are monotonically increasing. Therefore, we can use the method of binary search to find the index \(\textit{left}\) of the first element in the array \(\textit{nums}\) that is greater than or equal to \(\textit{target}\), and the index \(\textit{right}\) of the first element in the array \(\textit{nums}\) that is greater than \(\textit{target}\). If \(\textit{right} - \textit{left} > \frac{n}{2}\), it means that the number of occurrences of the element \(\textit{target}\) in the array \(\textit{nums}\) exceeds half of the length of the array, so return \(\textit{true}\), otherwise return \(\textit{false}\).
The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | |
1 2 3 4 5 6 7 8 | |
1 2 3 4 5 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | |
Solution 2: Binary Search (Optimized)
Thinking
Method 1 runs two binary searches. If \(\textit{target}\) occurs more than half the time, the index \(\textit{left}+\lfloor n/2\rfloor\) still holds \(\textit{target}\). One bisect_left plus that probe drops the second search.
In Solution 1, we used binary search twice to find the index \(\textit{left}\) of the first element in the array \(\textit{nums}\) that is greater than or equal to \(\textit{target}\), and the index \(\textit{right}\) of the first element in the array \(\textit{nums}\) that is greater than \(\textit{target}\). However, we can use binary search once to find the index \(\textit{left}\) of the first element in the array \(\textit{nums}\) that is greater than or equal to \(\textit{target}\), and then judge whether \(\textit{nums}[\textit{left} + \frac{n}{2}]\) is equal to \(\textit{target}\). If they are equal, it means that the number of occurrences of the element \(\textit{target}\) in the array \(\textit{nums}\) exceeds half of the length of the array, so return \(\textit{true}\), otherwise return \(\textit{false}\).
The time complexity is \(O(\log n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the array \(\textit{nums}\).
1 2 3 4 5 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | |