leetcode2529--正整数和负整数的最大计数

1. 题意

给定有序数组，求其中正整数和负整数的计数最大值。

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

2. 题解

2.1 遍历

直接判断

class Solution {
public:int maximumCount(vector<int>& nums) {int neg = 0;int pos = 0;for (int num:nums) {if (!num)continue;if (num & 0x80000000 )neg++;elsepos++;}return neg < pos ? pos : neg;}
};

2.2 二分查找

二分查找第一个非负值和第一个正值。

class Solution {
public:bool check(int l, int r, vector<int> &nums, int target){int sum = 0;for (int i = l; i < r + 1; ++i)sum += nums[i];return sum >= target;}int minSubArrayLen(int target, vector<int>& nums) {int l = 0;int sum = 0;int sz = nums.size();int ans = INT_MAX;vector<int> pre(sz + 1, 0);int preSum = 0;for (int i = 0;i < sz; ++i) {preSum += nums[i];pre[i + 1] = preSum;}for (int i = 0;i < sz; ++i) {int l = i;int r = sz;while (l < r) {int m = ((r - l) >> 1) + l;// cout << "m"<< m << "," << "sum" << sum << endl; if ( pre[m + 1] - pre[i] < target)l = m + 1;elser = m;}// printf("%d,%d\n", i, l);if ( l < sz){ans = min(l - i + 1, ans);}}return ans == INT_MAX ? 0 : ans;}
};

使用库函数

class Solution {
public:int maximumCount(vector<int>& nums) {auto non_neg = lower_bound(nums.begin(), nums.end(), 0) - nums.begin();auto pos = upper_bound(nums.begin(), nums.end(), 0);return max(non_neg, nums.end()- pos);}
};