2529.md

title	description	keywords
2529. 正整数和负整数的最大计数	LeetCode 2529. 正整数和负整数的最大计数题解，Maximum Count of Positive Integer and Negative Integer，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2529. 正整数和负整数的最大计数 正整数和负整数的最大计数 Maximum Count of Positive Integer and Negative Integer 解题思路 数组 二分查找 计数

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

🟢 Easy  🔖  数组 二分查找 计数  🔗 力扣 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	统计有序矩阵中的负数	[✓]	数组 二分查找 矩阵	🟢	🀄️ 🔗