题目链接 | 2529. 正整数和负整数的最大计数 |
---|---|
思路 | 二分法 |
题解链接 | 标准库调用 |
关键点 | 0的处理 |
时间复杂度 | \(O(\log n)\) |
空间复杂度 | \(O(1)\) |
代码实现:
class Solution:
def maximumCount(self, nums: List[int]) -> int:
def lower_bound(val):
left, right = -1, len(nums)
while left + 1 < right:
mid = (left+right) // 2
if nums[mid] < val:
left = mid
else:
right = mid
return right
zero_index = lower_bound(0)
n_neg = zero_index
while n_neg > 1 and nums[n_neg-1] == 0:
n_neg -= 1
ori_zero_index = zero_index
while zero_index < len(nums) and nums[zero_index] == 0:
zero_index += 1
n_pos = len(nums) - zero_index
return max(n_neg, n_pos)
Python-标准库
class Solution:
def maximumCount(self, nums: List[int]) -> int:
left, right = bisect_left(nums, 0), bisect_right(nums, 0)
return max(0, left, len(nums)-right)