1093. Statistics from a Large Sample

You are given a large sample of integers in the range [0, 255]. Since the sample is so large, it is represented by an array count where count[k] is the number of times that k appears in the sample.

Calculate the following statistics:

• minimum: The minimum element in the sample.
• maximum: The maximum element in the sample.
• mean: The average of the sample, calculated as the total sum of all elements divided by the total number of elements.
• median:

• If the sample has an odd number of elements, then the median is the middle element once the sample is sorted.
• If the sample has an even number of elements, then the median is the average of the two middle elements once the sample is sorted.

• mode: The number that appears the most in the sample. It is guaranteed to be unique.

Return the statistics of the sample as an array of floating-point numbers [minimum, maximum, mean, median, mode]. Answers within 10-5 of the actual answer will be accepted.

class Solution {
    double helper(vector<int> A, long long count) {
        int find1 = (count+1) / 2, find2 = count & 1 ? find1 : find1 + 1;
        int median1 = 0, median2 = 0;
        for(int i = 0; i < A.size(); i++) {
            if(A[i] < find1) find1-=A[i];
            else if(find1) {
                find1 = 0;
                median1 = i;
            }
            if(A[i] < find2) find2-=A[i];
            else if(find2) {
                find2 = 0;
                median2 = i;
            }
        }
        return (median1 + median2) / 2.0;
    }
public:
    vector<double> sampleStats(vector<int>& A) {
        double mi = DBL_MAX, ma = DBL_MIN, mode = 0, n = A.size();
        long long sum = 0, count = 0;
        for(int i = 0; i < n; i++) {
            if(!A[i]) continue;
            mi = min(mi, 1.0*i);
            ma = max(ma, 1.0*i);
            sum += 1ll * i * A[i];
            count += A[i];
            if(A[mode] < A[i]) mode = i;
        }
        double avg = 1.0 * sum / count;
        double median = helper(A, count);
        return {mi,ma,avg,median,mode};
    }
};