目标
给你一个按 非递减顺序 排列的数组 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 按 非递减顺序 排列。
进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？
思路
这个题简单做法就是循环计数，O(n)的时间复杂度。O(log(n))需要使用二分查找。Arrays.binarySearch() 是处理不了非严格递增的情况的，如果查找的key有多个，无法保证返回的是哪一个，通常就是中间的那一个。
这里的难点是弄清楚当有多个相同值的时候如何找到第一个。具体来说就是 low 与 high 的更新以及结束条件，自己可以用一个具体的例子来模拟查找的过程。
- 结束条件是
low == high。 - 如果寻找下界，那么
nums[middle] >= key更新high = middle，nums[middle] < key更新low = middle + 1。返回第一个大于等于key的index。 如果寻找上界，那么寻找上界的话只需将等号去掉即可，得到的是第一个小于等于key的index+1。nums[middle] > key更新high = middle - 1，nums[middle] <= key更新low = middle。
为什么要 +1 或者 -1？ 因为middle指的位置不等于key，不是我们要找的值，不应该再出现在下一次的查找范围内，这是能说的通的。其实最核心的目的是保证最终low、high指向同一个位置，防止出现low与high相差1，但是middle指向的位置也无法触发更新的情况。以[-3,0,0,3,4]为例，我们要找0的下界，如果low的更新不 +1，那么最终就是 low,middle 指向 -3，high 指向第一个0，这不是我们想要的。
代码
/**
* @date 2024-04-09 1:33
*/
public class MaximumCount2529 {
public int maximumCount(int[] nums) {
int pos = 0;
int neg = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] < 0) {
neg++;
} else if (nums[i] > 0) {
pos = nums.length - i;
break;
}
}
return Math.max(pos, neg);
}
/**
* 二分查找
*/
public int maximumCount_v2(int[] nums) {
int neg = bs(nums, 0);
int pos = bs(nums, 1);
return Math.max(neg, nums.length - pos);
}
public int bs(int[] nums, int key) {
int low = 0, high = nums.length;
while (low != high) {
int middle = (low + high) >> 1;
if (nums[middle] >= key) {
high = middle;
} else {
low = middle + 1;
}
}
return low;
}
}
性能
