1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int first = binarySearchFloor(nums, target);
if (first == -1)
return false;
int second = first + nums.length / 2;
if (second >= nums.length || nums[second] != target)
return false;
return true;
}
private int binarySearchFloor(int[] nums, int target) {
int left = 0, right = nums.length - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
ans = mid;
right = mid - 1;
}
}
return ans;
}
}
|
看到sorted, 就是binary search. 找到值等于target的最小index. 如果是majority, 那么另一端的index是second. 就有second - first + 1 > nums.length / 2. 于是second需要大于等于first + nums.length / 2. 我们就看这个位置是不是出界或者不等于target, 满足任意一个就返回false, 否则就是true.
时间复杂度: O(logn)
空间复杂度: O(1)
