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

正整数和负整数的最大记录

题目描述

给你一个按非递减顺序排列的数组 nums ，返回正整数数目和负整数数目中的最大值。 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg 二者中的最大值。 注意：0 既不是正整数也不是负整数。 示例 1： 输入：nums = [-2,-1,-1,1,2,3] 输出：3 解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。 示例 2： 输入：nums = [5,20,66,1314] 输出：4 解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

解题思路

1. 直接遍历数组，统计正整数和负整数的个数，然后返回较大的那个数。时间复杂度为O(n)，空间复杂度为O(1)。
2. 直接便利数组并没有利用数组按非递减顺序排列这个性质。我们可以将问题转换为以下两个问题（分治思想）：找到数组中最大负数所在的index：i，以及找到数组中最小正数所在的index：j，假设数组长度为n，则最终应该return max(i+1, n-j)。

    def find_max_neg(num):
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2

• 在闭区间[0, len(nums)]中查找，即[left, right]，这样的话可以保证最终的答案位于left处。

    if num[mid] < 0:
        left = mid + 1
    else:
        right = mid - 1
    return left

• 这里的判断条件可以根据自己的需要，写>=0，>0，<=0，<0，但是相应的left和right的更新方式要改变。比如本代码中写的是<0，因为我们想要找一个最大的负数，这说明从[left, mid]中的所有数都是严格<0的，因此要更新left，否则更新right。
• left和right的更新方式都是为了严格缩小搜索范围。

    max_neg = find_max_neg(nums)
    min_pos = find_min_pos(nums)
    return max(max_neg, (len(nums) - min_pos))

• 时间复杂度为O(logn)，空间复杂度为O(1)。

3. 结合思路2中的分析，直接调用python的内置函数bisect_left

    neg = bisect_left(nums, 0)
    pos = len(nums) - bisect_right(nums, 0)
    return max(neg, pos)

• bisect_left(nums, 0)用于找到第一个大于或等于0的位置的索引。而 bisect_right(nums, 0) 则用于找到第一个严格大于0的位置的索引。
• bisect_left和bisect_right都是Python中的二分查找函数，时间复杂度为O(logn)，空间复杂度为O(1)。