2529. 正整数和负整数的最大计数

🟢   🔖  数组 二分查找 计数  🔗 力扣 LeetCode

题目

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 nums is pos and the number of negative integers is neg, then return the maximum of pos and neg.

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] <= 2000
• nums is sorted in a non-decreasing order.

Follow up: Can you solve the problem in O(log(n)) time complexity?

题目大意

给你一个按 非递减顺序 排列的数组 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)) 的算法解决此问题吗？

解题思路

1. 二分查找负数的个数

首先，我们使用二分查找找出数组中负数的个数。

• 由于数组是非递减排序的，负数都集中在数组的左侧。
• 我们使用二分查找找到第一个非负数的位置（即 >= 0 的最左索引 left）。
• 这个索引 left 也就是负数的个数。

2. 二分查找正数的个数

接着，我们再次使用二分查找找出数组中正数的个数。

• 这次，我们找到第一个正数的位置（即 > 0 的最左索引 left）。
• 由于 left 是第一个正数的位置，因此正数的个数等于 n - left。

3. 比较负数和正数的个数，返回较大值

最后，取 negative 和 positive 之间的最大值，作为结果返回。

复杂度分析

• 时间复杂度：O(log n)，每次二分查找的时间复杂度为 O(log n)，总共执行两次二分查找，仍然是 O(log n)。
• 空间复杂度：O(1)，我们只使用了常数额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumCount = function (nums) {
	const n = nums.length;

	// 二分查找负数的个数
	let left = 0,
		right = n - 1;
	while (left <= right) {
		const mid = ((left + right) / 2) | 0;
		if (nums[mid] < 0) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	const negative = left;

	// 二分查找正数的个数
	(left = 0), (right = n - 1);
	while (left <= right) {
		const mid = ((left + right) / 2) | 0;
		if (nums[mid] <= 0) {
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	const positive = n - left;

	// 比较负数和正数的个数，返回较大值
	return Math.max(negative, positive);
};

相关题目

题号	标题	题解	标签	难度	力扣
704	二分查找	[✓]	数组 二分查找	🟢	🀄️ 🔗
1351	统计有序矩阵中的负数	[✓]	数组 二分查找 矩阵	🟢	🀄️ 🔗