2256. Minimum Average Difference

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumAverageDifference(vector<int>& nums) {
        int n = nums.size();
        if(n==1) return 0;
        long total = 0, ret = INT_MAX , ans = -1;
        for(const auto n:nums) total+=n;
        long lsum = 0, rsum = total;
        for(int i=0;i<n;++i){
            lsum+=nums[i];
            rsum-=nums[i];
            int lv , rv ;
            lv = lsum/(i+1);
            if(i==n-1) rv = 0.0;
            else rv = rsum/(n-i-1);
            if(abs(lv-rv) < ret){
                ret = abs(lv-rv);
                ans = i;
            }
            
        }
        return ans;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)