【Leetcode Daily】2529正整数和负整数的最大计数

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整数数组，求其中负整数和正整数数目中的最大值，0 不属于两者。

思路分享

• 本题暴力枚举也能 ac，下面就说说二分的写法。

• 就是解决两个问题，一是如何二分查找，二是如何利用二分找一个目标值的左部和右部。都在【Leetcode Daily】34在排序数组中查找元素的第一个和最后一个位置有所回答。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int lowerBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right-left)/2;
            if (nums[mid] < target) {
                left = mid+1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
    int maximumCount(vector<int>& nums) {
        int neg = lowerBound(nums, 0);
        int pos = nums.size()-lowerBound(nums, 1);
        //cout << neg << " " << pos << endl;
        return max(neg, pos);
    }
};