正整数和负整数的最大计数
难度:
标签:
题目描述
Given an array nums sorted in non-decreasing order, return the maximum between the number of positive integers and the number of negative integers.
- In other words, if the number of positive integers in
numsisposand the number of negative integers isneg, then return the maximum ofposandneg.
Note that 0 is neither positive nor negative.
Example 1:
Input: nums = [-2,-1,-1,1,2,3] Output: 3 Explanation: There are 3 positive integers and 3 negative integers. The maximum count among them is 3.
Example 2:
Input: nums = [-3,-2,-1,0,0,1,2] Output: 3 Explanation: There are 2 positive integers and 3 negative integers. The maximum count among them is 3.
Example 3:
Input: nums = [5,20,66,1314] Output: 4 Explanation: There are 4 positive integers and 0 negative integers. The maximum count among them is 4.
Constraints:
1 <= nums.length <= 2000-2000 <= nums[i] <= 2000numsis sorted in a non-decreasing order.
Follow up: Can you solve the problem in O(log(n)) time complexity?
代码结果
运行时间: 25 ms, 内存: 16.2 MB
/*
题目思路：
使用Java Stream，我们可以通过filter和count方法来分别计算正整数和负整数的数量，最后返回二者中的较大值。
*/
import java.util.Arrays;
public class Solution {
public int maximumCount(int[] nums) {
long pos = Arrays.stream(nums).filter(num -> num > 0).count();
long neg = Arrays.stream(nums).filter(num -> num < 0).count();
return (int) Math.max(pos, neg);
}
}解释
方法:
此题解利用了二分查找方法，通过 Python 的 bisect 模块来高效地确定正数和负数的数量。由于数组已经按非递减顺序排列，可以使用 bisect_left 来查找第一个非负数（0或正数）的位置，这个位置也表示负数的数量。同理，使用 bisect_right 查找第一个大于0的位置，用数组长度减去这个位置得到正数的数量。最后，比较这两个数量，取最大值返回。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在这个问题中选择使用二分查找来计算正负数的数量，而不是简单地遍历整个数组？
▷🦆
在使用`bisect_left`查找第一个非负数的位置时，如何保证它确实指向了0而不是正数，尤其是在没有0的情况下？
▷🦆
在调用`bisect_right(nums, 0)`时，如果数组中包含一个或多个0，这会如何影响正数的计数？
▷🦆
对于一个全是正数或全是负数的数组，这种方法处理的效率如何，有没有更高效的处理方式？
▷