class Solution {
public:
int maximumCount(vector<int>& nums) {
}
};
6283. 正整数和负整数的最大计数
给你一个按 非递减顺序 排列的数组 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] <= 2000nums 按 非递减顺序 排列。原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 43.9 MB, 提交时间: 2024-04-09 09:50:38
public class Solution {
public int maximumCount(int[] nums) {
int neg = lowerBound(nums, 0);
// 第一个 > 0 的位置，等价于第一个 >= 1 的位置
int pos = nums.length - lowerBound(nums, 1);
return Math.max(neg, pos);
}
// 返回 nums 中第一个 >= target 的数的下标
// 如果不存在这样的数，返回 nums.length
// 详见 https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(int[] nums, int target) {
// 二分范围：开区间 (left, right)
int left = -1;
int right = nums.length;
// 开区间不为空
while (left + 1 < right) {
// 循环不变量：
// nums[left] < target
// nums[right] >= target
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
// 二分范围缩小至 (left, mid)
right = mid;
} else {
// 二分范围缩小至 (mid, right)
left = mid;
}
}
// 此时 left 等于 right - 1
// 因为 nums[right - 1] < target 且 nums[right] >= target，所以答案是 right
return right;
}
}
javascript 解法, 执行用时: 51 ms, 内存消耗: 51.4 MB, 提交时间: 2024-04-09 09:50:22
/**
* @param {number[]} nums
* @return {number}
*/
var maximumCount = function(nums) {
const neg = lowerBound(nums, 0);
// 第一个 > 0 的位置，等价于第一个 >= 1 的位置
const pos = nums.length - lowerBound(nums, 1);
return Math.max(neg, pos);
};
// 返回 nums 中第一个 >= target 的数的下标
// 如果不存在这样的数，返回 nums.length
// 详见 https://www.bilibili.com/video/BV1AP41137w7/
function lowerBound(nums, target) {
// 二分范围：开区间 (left, right)
let left = -1;
let right = nums.length;
// 开区间不为空
while (left + 1 < right) {
// 循环不变量：
// nums[left] < target
// nums[right] >= target
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= target) {
// 二分范围缩小至 (left, mid)
right = mid;
} else {
// 二分范围缩小至 (mid, right)
left = mid;
}
}
// 此时 left 等于 right - 1
// 因为 nums[right - 1] < target 且 nums[right] >= target，所以答案是 right
return right;
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-04-09 09:50:05
impl Solution {
pub fn maximum_count(nums: Vec<i32>) -> i32 {
let neg = nums.partition_point(|&x| x < 0);
let pos = nums.len() - nums.partition_point(|&x| x <= 0);
neg.max(pos) as _
}
}
cpp 解法, 执行用时: 7 ms, 内存消耗: 19.8 MB, 提交时间: 2024-04-09 09:49:50
class Solution {
public:
int maximumCount(vector<int> &nums) {
int neg = ranges::lower_bound(nums, 0) - nums.begin();
int pos = nums.end() - ranges::upper_bound(nums, 0);
return max(neg, pos);
}
};
python3 解法, 执行用时: 40 ms, 内存消耗: 16.7 MB, 提交时间: 2024-04-09 09:49:28
class Solution:
def maximumCount(self, nums: List[int]) -> int:
neg = bisect_left(nums, 0)
pos = len(nums) - bisect_right(nums, 0)
return max(neg, pos)
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-04-09 09:49:03
impl Solution {
pub fn maximum_count(nums: Vec<i32>) -> i32 {
let mut neg = 0;
let mut pos = 0;
for &x in &nums {
if x < 0 {
neg += 1;
} else if x > 0 {
pos += 1;
}
}
neg.max(pos)
}
}
javascript 解法, 执行用时: 65 ms, 内存消耗: 51.5 MB, 提交时间: 2024-04-09 09:48:51
/**
* @param {number[]} nums
* @return {number}
*/
var maximumCount = function(nums) {
let neg = 0;
let pos = 0;
for (const x of nums) {
if (x < 0) {
neg++;
} else if (x > 0) {
pos++;
}
}
return Math.max(neg, pos);
};
cpp 解法, 执行用时: 7 ms, 内存消耗: 19.8 MB, 提交时间: 2024-04-09 09:48:39
class Solution {
public:
int maximumCount(vector<int> &nums) {
int neg = 0, pos = 0;
for (int x : nums) {
if (x < 0) {
neg++;
} else if (x > 0) {
pos++;
}
}
return max(neg, pos);
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 43.9 MB, 提交时间: 2024-04-09 09:48:11
public class Solution {
public int maximumCount(int[] nums) {
int neg = 0;
int pos = 0;
for (int x : nums) {
if (x < 0) {
neg++;
} else if (x > 0) {
pos++;
}
}
return Math.max(neg, pos);
}
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15.2 MB, 提交时间: 2023-01-09 10:21:55
class Solution:
def maximumCount(self, nums: List[int]) -> int:
return max(bisect_left(nums, 0), len(nums) - bisect_right(nums, 0))
golang 解法, 执行用时: 20 ms, 内存消耗: 6.1 MB, 提交时间: 2023-01-09 10:21:40
func maximumCount(nums []int) int {
return max(sort.SearchInts(nums, 0), len(nums)-sort.SearchInts(nums, 1))
}
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 16 ms, 内存消耗: 6.1 MB, 提交时间: 2023-01-09 10:21:29
func maximumCount(nums []int) int {
less, great := 0, 0
for _, x := range nums {
if x < 0 {
less++
} else if x > 0 {
great++
}
}
return max(less, great)
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 32 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-09 10:21:11
class Solution:
def maximumCount(self, nums: List[int]) -> int:
less = great = 0
for x in nums:
if x < 0: less += 1
elif x > 0: great += 1
return max(less, great)
python3 解法, 执行用时: 44 ms, 内存消耗: 15.2 MB, 提交时间: 2023-01-09 10:20:41
class Solution:
def maximumCount(self, nums: List[int]) -> int:
pos = len([k for k in nums if k > 0])
zero = len([k for k in nums if k == 0])
return max(len(nums)-pos-zero, pos)