C++ solution O(nm) whose result is accurate.(m is related to the nums)


  • 0
    K
    double findMaxAverage(vector<int>& nums, int k) {
            int i, j;
            vector<int> cumsum(nums.size() + 1, 0);
            vector<int> index(nums.size(), 0);
            vector<double> average(nums.size(), 0.0);
            double temp, result = INT_MIN;
            
            // cumulate sum 
            for(i = 0; i < nums.size(); i++) cumsum[i + 1] = cumsum[i] + nums[i];
            
            // calculate the maximum average end with the i_th num, the length is unlimited
            for(i = 0; i < nums.size() - k; i++) {
                index[i] = i;
                average[i] = nums[i];
                j = i - 1;
                while(j >= 0 && average[j] >= average[i]) {
                    average[i] = (cumsum[i + 1] - cumsum[index[j]]) / (i - index[j] + 1.0);
                    index[i] = index[j];
                    j = index[j] - 1;
                }
            }
            
            // calculate the maximum average end with the i_th num, the length is greater than or equal to k
            for(i = k - 1; i < nums.size(); i++) {
                temp = double(cumsum[i + 1] - cumsum[i - k + 1]) / k;
                j = i - k;
                while(j >= 0 && average[j] >= temp) {
                    temp = (cumsum[i + 1] - cumsum[index[j]]) / (i - index[j] + 1.0);
                    j = index[j] - 1;
                }
                result = temp > result ? temp : result;
            }
            
            return result;
        }
    

  • 0

    @kevincabbage
    What is the running time? I guess it might be better if using the binary search.


  • 0
    K

    @Hao-Cai The running time is round 100ms, at least beats 90%. The time of binary search is almost same. But the result is more accurate. Of course, both methods satisfy the 10-5 requirment.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.