class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
}
};
1150. 检查一个数是否在数组中占绝大多数
给出一个按 非递减 顺序排列的数组 nums，和一个目标数值 target。假如数组 nums 中绝大多数元素的数值都等于 target，则返回 True，否则请返回 False。
所谓占绝大多数，是指在长度为 N 的数组中出现必须 超过 N/2 次。
示例 1：
输入：nums = [2,4,5,5,5,5,5,6,6], target = 5 输出：true 解释： 数字 5 出现了 5 次，而数组的长度为 9。 所以，5 在数组中占绝大多数，因为 5 次 > 9/2。
示例 2：
输入：nums = [10,100,101,101], target = 101 输出：false 解释： 数字 101 出现了 2 次，而数组的长度是 4。 所以，101 不是 数组占绝大多数的元素，因为 2 次 = 4/2。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10^91 <= target <= 10^9原站题解
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-10-15 19:09:06
class Solution:
def isMajorityElement(self, nums: List[int], target: int) -> bool:
return nums.count(target) > len(nums) / 2
python3 解法, 执行用时: 44 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-15 19:09:00
class Solution:
def isMajorityElement(self, nums: List[int], target: int) -> bool:
n = len(nums)
#L = bisect.bisect_left(nums, target)
#R = bisect.bisect_right(nums, target)
L = self.binary_search_left(nums, target)
R = self.binary_search_right(nums, target)
cur_len = R - L
return cur_len > n // 2
def binary_search_left(self, nums: List[int], target: int) -> int:
L, R = 0, len(nums)
while L < R:
mid = (L + R) >> 1
if nums[mid] >= target: #寻找符合条件最左端
R = mid
else:
L = mid + 1
return L
def binary_search_right(self, nums: List[int], target: int) -> int:
L, R = 0, len(nums)
while L < R:
mid = (L + R) >> 1
if nums[mid] > target: #寻找符合提交的最左端
R = mid
else:
L = mid + 1
return L
java 解法, 执行用时: 1 ms, 内存消耗: 39.8 MB, 提交时间: 2023-10-15 19:07:56
class Solution {
public boolean isMajorityElement(int[] nums, int target) {
int cn = (int) Arrays.stream(nums).filter(a -> a == target).count();
return cn * 2 > nums.length;
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.8 MB, 提交时间: 2023-10-15 19:07:38
class Solution {
public:
bool isMajorityElement(vector<int>& nums, int target) {
return (upper_bound(nums.begin(), nums.end(), target) - lower_bound(nums.begin(), nums.end(), target)) * 2 > nums.size();
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-15 19:07:27
func isMajorityElement(nums []int, target int) bool {
left := binarySearchLeft(nums, target)
return left != -1 && left + len(nums)/2 < len(nums) && nums[left + len(nums)/2] == target
}
func binarySearchLeft(nums []int, target int) int {
l, r := 0, len(nums) - 1
for l <= r {
mid := l + (r - l)/2
if nums[mid] >= target {
r = mid - 1
} else {
l = mid + 1
}
}
if l < len(nums) && nums[l] == target {
return l
}
return -1
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-15 19:07:14
func isMajorityElement(nums []int, target int) bool {
left, right := binarySearchLeft(nums, target), binarySearchRight(nums, target)
return left != -1 && right != -1 && right - left + 1 > len(nums)/2
}
func binarySearchLeft(nums []int, target int) int {
l, r := 0, len(nums) - 1
for l <= r {
mid := l + (r - l)/2
if nums[mid] >= target {
r = mid - 1
} else {
l = mid + 1
}
}
if l < len(nums) && nums[l] == target {
return l
}
return -1
}
func binarySearchRight(nums []int, target int) int {
l, r := 0, len(nums) - 1
for l <= r {
mid := l + (r - l)/2
if nums[mid] <= target {
l = mid + 1
} else {
r = mid - 1
}
}
if r >= 0 && nums[r] == target {
return r
}
return r - 1
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-15 19:07:00
// 遍历
func isMajorityElement1(nums []int, target int) bool {
count := 0
for i := 0; i < len(nums); i++ {
if nums[i] == target {
count++
}
}
return count > len(nums)/2
}
// 遍历到目标
func isMajorityElement2(nums []int, target int) bool {
count := 0
for i := 0; i < len(nums); i++ {
if nums[i] == target {
count++
} else if nums[i] > target {
break
}
}
return count > len(nums)/2
}
// 双指针
func isMajorityElement(nums []int, target int) bool {
if len(nums) == 1 {
return nums[0] == target
}
left, right := 0, len(nums) - 1
for left < right {
if nums[left] < target {
left++
} else if nums[left] > target {
return false
}
if nums[right] > target {
right--
} else if nums[right] < target {
return false
}
if nums[left] == target && nums[right] == target {
break
}
}
return right - left + 1 > len(nums) / 2
}