【2024.04.09】LeetCode每日一题·正整数和负整数的最大计数

2024年04月09日 21时10分

标签： LeetCode 数组二分模拟

## 题目描述

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

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

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

#### 示例1
````
输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。
````

#### 示例2
````
输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
````

#### 示例3
````
输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
````

#### 提示
````
1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：[2529. 正整数和负整数的最大计数](https://leetcode.cn/problems/maximum-count-of-positive-integer-and-negative-integer/description/?envType=daily-question&envId=2024-04-09)

## 解题思路1
最简单直接遍历数组统计正整数和负整数个数即可。时间复杂度$$O(n)$$，空间复杂度$$O(1)$$。

### 代码
````cpp
class Solution {
public:
    int maximumCount(vector<int>& nums) {
        int pos = 0, neg = 0;
        for(int num: nums){
            if(num < 0) neg++;
            else if(num > 0) pos++;
        }
        return max(pos, neg);
    }
};
````

### 用时和内存
> 执行用时：18 ms，在所有C++提交中击败了13.17%的用户
>
> 内存消耗：19.63 MB，在所有C++提交中击败90.35%的用户
>

## 解题思路2
另外可以利用数组**非递增排序**的性质，二分小于0的最大数的下标和大于0的最小数的下标，即可得到答案。时间复杂度$$O(\log n)$$，空间复杂度$$O(1)$$

### 代码
````cpp
class Solution {
public:
    int findMaxSmallerThan0(vector<int>& nums){
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] < 0){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return r;
    }
    int findMinLargerThan0(vector<int>& nums){
        int l = 0, r = nums.size() - 1;
        while(l <= r){
            int mid = (r - l) / 2 + l;
            if(nums[mid] > 0){
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
    int maximumCount(vector<int>& nums) {
        int pos = nums.size() - findMinLargerThan0(nums), neg = findMaxSmallerThan0(nums) + 1;
        return max(pos, neg);
    }
};
````

### 用时和内存
> 执行用时：7 ms，在所有C++提交中击败了96.10%的用户
>
> 内存消耗：19.79 MB，在所有C++提交中击败25.42%的用户
>

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.04.09】LeetCode每日一题·正整数和负整数的最大计数

所有评论

暂无评论

新增评论