难度: Easy
Submission
运行时间: 22 ms
内存: 16.1 MB
class Solution:
def isMajorityElement(self, nums: List[int], target: int) -> bool:
def binarySearchLeft(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# 二分查找找到target最后一次出现的位置
def binarySearchRight(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid
return left
left_idx = binarySearchLeft(nums, target)
right_idx = binarySearchRight(nums, target)
# 如果target在数组中出现了超过N/2次，则返回True，否则返回False
return (right_idx - left_idx) > len(nums) // 2
Explain
本题解利用二分查找算法来定位目标数字target在有序数组nums中的起始和结束位置。首先，通过一个辅助函数binarySearchLeft找到target首次出现的位置（如果存在）。接着，通过另一个辅助函数binarySearchRight找到target最后一次出现的位置加一（相当于下一个不同元素的位置，或数组边界）。最后，计算这两个位置的差值，即target在数组中出现的次数。如果这个次数超过数组长度的一半，则函数返回True，表示target占绝大多数；否则返回False。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def isMajorityElement(self, nums: List[int], target: int) -> bool:
def binarySearchLeft(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # target比中点大，搜索右半区
else:
right = mid # target小于等于中点，搜索左半区
return left
def binarySearchRight(nums, target):
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1 # target小于等于中点，搜索右半区
else:
right = mid # target比中点大，搜索左半区
return left
left_idx = binarySearchLeft(nums, target)
right_idx = binarySearchRight(nums, target)
return (right_idx - left_idx) > len(nums) // 2 # 比较target出现次数是否超过数组长度的一半
Explore
在这种情况下，`binarySearchLeft` 和 `binarySearchRight` 函数会返回相同的索引值，该值指向数组中第一个大于 `target` 的元素位置。如果 `target` 大于数组中所有元素，这两个函数返回的索引值会是数组长度。因此，当 `left_idx` 等于 `right_idx` 时，表示 `target` 在数组中不存在，因此 `target` 出现次数为零。这样，通过检查 `right_idx - left_idx` 是否大于 `len(nums) // 2`，可以正确判断 `target` 是否占绝大多数，即使 `target` 不存在也不会错误返回位置。
算法中使用的是 `len(nums) // 2` 来确定多数的阈值。在数组长度为偶数时，这个值恰好是数组长度的一半；如果数组长度为奇数，这个值是数组长度除以 2 向下取整的结果。因此，只有当 `target` 出现的次数严格大于 `len(nums) // 2` 时，才返回 `True`。这意味着在边界情况下，例如当 `target` 出现次数恰好为数组长度的一半（不论数组长度是奇数还是偶数）时，算法仍会返回 `False`。因此，该算法在处理边界条件时是准确的，不会因为整数除法向下取整而产生错误判断。
返回 `target` 最后一次出现位置的下一个位置是常用的技术，用以计算元素的计数或确定范围。这种方法本身不会导致误判元素数量。它确保我们可以通过 `right_idx - left_idx` 直接得到 `target` 在数组中的出现次数。此外，即使 `target` 在数组中不存在，上述方法也能正确返回出现次数为 0，因为 `left_idx` 和 `right_idx` 将相等。因此，无论数组情况如何，这种处理方式都不会导致元素数量的误判。