两次二分，LeetCode 2529. 正整数和负整数的最大计数

一、题目

1、题目描述

给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。

• 换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。

注意：0 既不是正整数也不是负整数。

2、接口描述

python3

​

class Solution:
    def maximumCount(self, nums: List[int]) -> int:

cpp

​

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        
    }
};

3、原题链接

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

二、解题报告

1、思路分析

二分找到第一个 ≥ 0 的数的下标 i，负数个数即i

二分找到第一个 > 0 的数的下标 i，正数个数即n - i

返回二者中大的那一个

2、复杂度

时间复杂度： O(logn)空间复杂度：O(1)

3、代码详解

python3

​

class Solution:
    def maximumCount(self, nums: List[int]) -> int:
        neg = bisect_left(nums, 0)
        pos = len(nums) - bisect_right(nums, 0)
        return max(pos, neg)

cpp

​

class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int neg = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();
        int pos = nums.end() - upper_bound(nums.begin(), nums.end(), 0);
        return max(neg, pos);
    }
};