LeetCode 2529题解：有序数组正负数统计与二分查找优化

1. 题目背景与问题描述今天我们来拆解LeetCode第2529题正整数和负整数的最大计数。这是一道典型的数组统计问题主要考察对数组元素的遍历和条件判断能力。题目要求我们统计一个已排序数组中正整数和负整数的数量并返回两者中的较大值。给定一个非递减顺序排列的整数数组nums我们需要统计数组中负整数的数量neg统计数组中正整数的数量pos返回max(neg, pos)注意0不被视为正数也不被视为负数所以遇到0时不做计数。2. 解题思路分析2.1 暴力解法最直观的解法是直接遍历整个数组使用两个计数器分别记录正负数的数量def maximumCount(nums): pos neg 0 for num in nums: if num 0: pos 1 elif num 0: neg 1 return max(pos, neg)时间复杂度O(n)需要完整遍历数组 空间复杂度O(1)只使用了常数空间2.2 利用有序特性优化由于数组是非递减排序的我们可以利用这个特性进行优化使用二分查找找到第一个非负数的位置这个位置之前的都是负数使用二分查找找到第一个正数的位置这个位置之后的都是正数计算neg和pos的数量import bisect def maximumCount(nums): neg bisect.bisect_left(nums, 0) pos len(nums) - bisect.bisect_right(nums, 0) return max(neg, pos)时间复杂度O(log n)使用了两次二分查找 空间复杂度O(1)3. 代码实现详解3.1 二分查找实现细节让我们详细看看二分查找的实现def find_first_non_negative(nums): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] 0: left mid 1 else: right mid return left def find_first_positive(nums): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] 0: left mid 1 else: right mid return left3.2 边界条件处理需要考虑的特殊情况数组全为正数数组全为负数数组包含0空数组4. 复杂度分析与比较方法时间复杂度空间复杂度适用场景暴力解法O(n)O(1)简单直接适合小规模数据二分查找O(log n)O(1)大规模数据性能更优5. 测试用例设计好的测试用例应该覆盖各种边界情况test_cases [ ([-2,-1,-1,1,2,3], 3), # 正常情况 ([-3,-2,-1,0,0,1,2], 3), # 包含0 ([5,20,66,1314], 4), # 全正数 ([-1,-1,-1], 3), # 全负数 ([0,0,0], 0), # 全0 ([], 0), # 空数组 ]6. 常见错误与调试技巧6.1 常见错误忘记处理0的情况二分查找的边界条件处理不当正负数计数时逻辑错误6.2 调试技巧打印中间变量检查二分查找的分界点使用小规模测试数据手动验证检查数组全正/全负的特殊情况7. 实际应用场景这类计数问题在实际开发中很常见比如用户评价统计好评/差评数量日志分析成功/失败请求计数金融交易记录收入/支出统计8. 性能优化进阶对于特别大的数组还可以考虑并行计算将数组分块多线程统计SIMD指令优化使用向量化指令加速遍历预处理如果数组不变可以预先计算并缓存结果9. 类似题目推荐统计有序矩阵中的负数LeetCode 1351在排序数组中查找元素的第一个和最后一个位置LeetCode 34山脉数组的峰顶索引LeetCode 85210. 个人解题心得在实际解决这个问题时我最初直接使用了暴力解法因为代码简单不易出错。后来考虑到题目给出的数组是有序的这个重要条件才想到可以使用二分查找优化。这提醒我在解题时一定要仔细阅读题目给出的所有条件特别是那些看似显而易见的条件往往就是优化的关键。另一个收获是关于二分查找边界条件的处理。在实现find_first_non_negative和find_first_positive时我最初混淆了两种情况的判断条件导致测试失败。通过这个小错误我更加理解了二分查找中寻找左边界和寻找右边界的区别。