正整数和负整数的最大计数-LeetCode

2529. 正整数和负整数的最大计数

🎯 问题描述（来源于LeetCode）

描述：
给你一个按非递减顺序排列的数组 nums。
请你判断正整数和负整数的数目，并返回正整数数目和负整数数目的最大值。

• 负整数：小于 0 的整数。
• 正整数：大于 0 的整数。
• 注意：0 既不是正整数也不是负整数。

说明：

• 这是一个二分查找问题。

• 核心逻辑是利用数组的有序性，通过二分查找快速定位 0 的边界。

• 通过两次二分查找，分别找到负整数的个数和正整数的个数。

• 示例：

• 示例 1：

输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：
- 负整数有 3 个：-2, -1, -1。
- 正整数有 3 个：1, 2, 3。
- 最大值为 3。

• 示例 2：

输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：
- 负整数有 3 个：-3, -2, -1。
- 正整数有 2 个：1, 2。
- 最大值为 3。

💻 解题思路

思路1：二分查找（下界）

思路1：代码实现

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        def lowerbond(nums: List[int], target: int):
            # 寻找第一个大于等于 target 的位置
            left = -1
            right = len(nums) 
            while left + 1 < right:
                mid = left + (right - left)//2
                if nums[mid] < target:
                    left = mid
                else:
                    right = mid 
            return right        
        
        # 1. 找到负整数的个数
        # 负整数是小于 0 的数，所以找到第一个 >= 0 的位置，该位置之前的都是负整数
        neg = lowerbond(nums, 0) 
        
        # 2. 找到正整数的个数
        # 正整数是大于 0 的数，所以找到第一个 >= 1 的位置，该位置及之后的都是正整数
        # 正整数个数 = 总长度 - 第一个 >= 1 的位置
        pos = len(nums) - lowerbond(nums, 1)
        
        # 3. 返回最大值
        return max(neg, pos)

思路1：📊 性能分析

• 时间复杂度：$O(\log N)$
  • 其中 $N$ 是数组 nums 的长度。
  • 代码中调用了两次 lowerbond 函数，每次都是二分查找，时间复杂度为 $O(\log N)$。
  • 总时间复杂度为 $O(2 \log N) \approx O(\log N)$。
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量，没有使用额外的数据结构。

思考

1. 二分查找模板：

   • 代码使用了开区间的二分查找模板：left = -1, right = len(nums)，循环条件为 while left + 1 < right。
   • 这种模板的优点是边界处理简单，不需要考虑 left == right 的情况。
   • 最终返回的 right 就是第一个大于等于 target 的位置。

2. 负整数计数：

   • neg = lowerbond(nums, 0) 找到第一个大于等于 0 的位置。
   • 该位置之前的元素都是小于 0 的，即负整数。
   • 所以负整数的个数就是 lowerbond(nums, 0)。

3. 正整数计数：

   • pos = len(nums) - lowerbond(nums, 1) 找到第一个大于等于 1 的位置。
   • 该位置及之后的元素都是大于等于 1 的，即正整数。
   • 所以正整数的个数就是 总长度 - 第一个大于等于 1 的位置。

4. 边界情况：

   • 数组全是负数：lowerbond(nums, 0) 返回 len(nums)，neg = len(nums)，pos = 0。
   • 数组全是正数：lowerbond(nums, 0) 返回 0，neg = 0，lowerbond(nums, 1) 返回 0，pos = len(nums)。
   • 数组全是 0：lowerbond(nums, 0) 返回 0，neg = 0，lowerbond(nums, 1) 返回 len(nums)，pos = 0。