2529. Maximum Count of Positive Integer and Negative Integer

發表於 | 分類於

problem

solution

  • naive
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
    public:
        int maximumCount(vector<int>& nums) {
            int ne_count = 0, pos_count = 0;
            for(int n:nums){
                if(n < 0) ne_count++;
                else if(n > 0) pos_count++;
            }
            return max(ne_count, pos_count);
            
        }
    };
  • binary search
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution {
    public:
        int maximumCount(vector<int>& nums) {
            int n = nums.size();
            // find first position large than 0 
            int l = 0, r = n;
            while(l<r){
                int mid = l + (r-l)/2;
                if(nums[mid] <= 0 ) l = mid +1;
                else r = mid;
            }
            l = r-1;
            while(l> -1 && nums[l] ==0) l--;
            
            return max(n-r, l+1);
            
        }
    };

    analysis

  • time complexity O(n) -> O(logn)
  • space complexity O(1)