因为需要O(logn)的复杂度,所以考虑使用二分法,先找到负数里面的最大下标(初始值定为-1),再找到第一个正数的下标(初始值定为数组长度值)。最后求出个数并进行比较即可。
class Solution {
public:
int maximumCount(vector<int>& nums) {
int pos1=-1;
int pos2=nums.size();
int left=0;
int right=nums.size()-1;
int mid=0;
//找最后一个负数
while(left<=right){
mid=(left+right)/2;
if(nums[mid]>=0){
right=mid-1;
}
else{
pos1=mid;
left=mid+1;
}
}
//找第一个正数
left=0;
right=nums.size()-1;
while(left<=right){
mid=(left+right)/2;
if(nums[mid]<=0){
left=mid+1;
}
else{
pos2=mid;
right=mid-1;
}
}
int num_fu=pos1+1;
int num_zheng=nums.size()-1-pos2+1;
return max(num_fu,num_zheng) ;
}
};