讨论/《高频算法实战》 - 练习:求数组区间方差/
《高频算法实战》 - 练习:求数组区间方差
共 3 个回复

看到那个C++评论后,突然好奇,我的为啥是双百AC呢?我的for循环明明套用了的:

class Solution {
public:
    vector<double> array_interval_std(vector<int>& nums, vector<vector<int>>& queries) {
        int length,n = queries.size();
        double mean,res;
        vector<double> vec;
        for(int i = 0;i<n;i++){
            mean=0;res=0;
            length = queries[i][1]-queries[i][0]+1;
            for(int j = queries[i][0]-1;j<queries[i][1];j++)
                mean += nums[j];
            mean /= length;
            for(int j = queries[i][0]-1;j<queries[i][1];j++)
                res += pow(mean-nums[j],2);
            res /= length;
            vec.push_back(res);
        }
        return vec;
            
    }
};

image.png

class Solution {
public double[] array_interval_std(int[] nums, int[][] queries) {

    int n = nums.length;
    int m = queries.length;

    int[] sum = new int[n];
    int[] dec = new int[m];
    sum[0] = nums[0];
    for (int i = 1; i <= n-1; i++) {
        sum[i] = sum[i-1] + nums[i]; 
    }
    
    for (int j = 0; j < m; j++) {
        dec[j] = sum[(queries[j][1] - 1)] - sum[(queries[j][0] - 1)] + nums[(queries[j][0] - 1)];
    }


    double[] result = new double[queries.length];
    for(int i = 0;i < queries.length;i++){
        int xpow=0;
        int left = queries[i][0];
        int right = queries[i][1];
        int length = right - left + 1;
        for(int j = left-1;j < right;j++){
            xpow += nums[j]*nums[j];
        }
        double set = length * length;
        double nums1=(double)xpow/length;
        double nums2=(double)(dec[i]*dec[i])/set;
        
        
        double res = nums1 - nums2;
        result[i] = res; 

    }
    return result;

}

}

class Solution {
public:
    vector<double> array_interval_std(vector<int>& nums, vector<vector<int>>& queries) {
        vector<int> sub_sum;
        vector<int> sub_squar_sum;
        sub_sum.push_back(0);
        sub_squar_sum.push_back(0);
        int cur_sum = 0, cur_suqar_sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            cur_sum += nums[i];
            sub_sum.push_back(cur_sum);
            cur_suqar_sum += nums[i] * nums[i];
            sub_squar_sum.push_back(cur_suqar_sum);
        }
        vector<double> res;
        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int n = r - l + 1;
            double ret = (sub_squar_sum[r] - sub_squar_sum[l-1]
                 - (sub_sum[r] - sub_sum[l-1])*(sub_sum[r] - sub_sum[l-1])*1.0/n) /n;
            res.push_back(ret);
        }
        return res;
    }
};