题目描述
给你一个按 非递减顺序 排列的数组 nums
,返回正整数数目和负整数数目中的最大值。
- 换句话讲,如果
nums
中正整数的数目是pos
,而负整数的数目是neg
,返回pos
和neg
二者中的最大值。
注意:0
既不是正整数也不是负整数。
思路
因为是一个非递减顺序的数组,因此看上去可以用二分查找去寻找最大的负数和最小的正数。
最开始的想法是分别二分搜索大于 0 和小于 0 的数,那这不就得实现两遍二分了嘛,能不能只实现一次呢?
看了答案,还真行,一次搜索大于等于 0 的数字,下一次搜索大于等于 1 的数字,这不就分别求出负整数的数量和正整数的数量了嘛,而且只需要实现一次二分搜索算法。
那么中间条件是什么呢?参考 搜索模板,我们的目标是寻找左边界,因此会更保守地更新右边界,直到 l<r
。
最终代码: