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 <= 109nums 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$.
1
2
3
4
5
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
}
|
1
2
3
4
5
6
7
8
| 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;
}
};
|
1
2
3
4
5
| func isMajorityElement(nums []int, target int) bool {
left := sort.SearchInts(nums, target)
right := sort.SearchInts(nums, target+1)
return right-left > len(nums)/2
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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$.
1
2
3
4
5
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
| 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;
}
};
|
1
2
3
4
5
6
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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;
}
|
