标签： upper bound

目标

给你一个按 非递减顺序 排列的数组 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。
• 如果寻找上界，那么 nums[middle] > key 更新 high = middle - 1，nums[middle] <= key 更新 low = middle。 寻找上界的话只需将等号去掉即可，得到的是第一个小于等于key的index+1。

为什么要 +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;
    }
}

性能