Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1093.html

1093. Statistics from a Large Sample

Level

Medium

Description

We sampled integers between 0 and 255, and stored the results in an array count: count[k] is the number of integers we sampled equal to k.

Return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers. The mode is guaranteed to be unique.

(Recall that the median of a sample is:

  • The middle element, if the elements of the sample were sorted and the number of elements is odd;
  • The average of the middle two elements, if the elements of the sample were sorted and the number of elements is even.)

Example 1:

Input: count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Output: [1.00000,3.00000,2.37500,2.50000,3.00000]

Example 2:

Input: count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]

Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

  1. count.length == 256
  2. 1 <= sum(count) <= 10^9
  3. The mode of the sample that count represents is unique.
  4. Answers within 10^-5 of the true value will be accepted as correct.

Solution

Loop over the array count twice.

For the first loop, obtain the minimum, maximum, sum, total count of sampled numbers and mode of the sample respectively. The mean can be calculated by the sum and the total count.

For the second loop, obtain the median using the total count and each number’s count. If the total count is odd, then simply find the number that is at the middle. If the total count is even, then check the two numbers at the middle, which may be the same or different, and calculate the average of the two numbers to obtain the median.

Finally, return the statistics.

  • class Solution {
    public double[] sampleStats(int[] count) {
        int length = count.length;
        double min = -1, max = -1, mode = -1;
        int modeCount = 0;
        double sum = 0;
        int totalCount = 0;
        for (int i = 0; i < length; i++) {
            int curCount = count[i];
            if (curCount > 0) {
                if (min < 0)
                    min = i;
                max = i;
                sum += i * curCount;
                totalCount += curCount;
                if (curCount > modeCount) {
                    modeCount = curCount;
                    mode = i;
                }
            }
        }
        double mean = sum / totalCount;
        double median = 0;
        int countMedian = 0;
        int prev = -1;
        for (int i = 0; i < length; i++) {
            int curCount = count[i];
            if (curCount > 0) {
                if (totalCount % 2 == 0) {
                    if (countMedian * 2 == totalCount) {
                        median = (prev + i) / 2.0;
                        break;
                    } else {
                        countMedian += curCount;
                        if (countMedian * 2 > totalCount) {
                            median = i;
                            break;
                        }
                    }
                } else {
                    countMedian += curCount;
                    if (countMedian * 2 > totalCount) {
                        median = i;
                        break;
                    }
                }
                prev = i;
            }
        }
        return new double[]{min, max, mean, median, mode};
    }
}

  • // OJ: https://leetcode.com/problems/statistics-from-a-large-sample/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<double> sampleStats(vector<int>& A) {
        int mx = 0, mn = 255, cnt = 0, total = accumulate(begin(A), end(A), 0), mid = (total + 1) / 2, mode = -1, first = -1;
        long sum = 0;
        double median = -1;
        for (int i = 0; i < A.size(); ++i) {
            if (A[i] == 0) continue;
            mx = max(mx, i);
            mn = min(mn, i);
            sum += (long)A[i] * i;
            if (median == -1) {
                if (first != -1) {
                    median = (double)(first + i) / 2;
                } else if (cnt < mid && cnt + A[i] >= mid) {
                    if (total % 2 || cnt + A[i] > mid) median = i;
                    else first = i;
                }
            }
            cnt += A[i];
            if (mode == -1 || A[i] > A[mode]) mode = i;
        }
        return { (double)mn, (double)mx, (double)sum / total, median, (double)mode };
    }
};

  • # 1093. Statistics from a Large Sample
# https://leetcode.com/problems/statistics-from-a-large-sample/

class Solution:
    def sampleStats(self, count: List[int]) -> List[float]:
        n = s = 0
        mp = collections.defaultdict(int)
        
        for i,x in enumerate(count):
            if x > 0:
                s += i * x
                mp[i] += x
                n += x
        
        mmin = min(mp)
        mmax = max(mp)
        mode = max(mp, key = mp.get)
        mean = s / n
        median = 0
        medianPos = (n // 2) if n % 2 != 0 else (n // 2 - 1, n // 2)
        
        if n & 1:
            curr = 0
            for key,v in mp.items():
                curr += v
                if curr > medianPos:
                    median = key
                    break
        else:
            curr = 0
            isNext = False
            for key, v in mp.items():
                if isNext:
                    median = (median + key) / 2
                    break
                curr += v
                if (curr > medianPos[0]):
                    if curr > medianPos[0] and curr <= medianPos[1]:
                        median = key
                        isNext = True
                    else:
                        median = key
                        break
            
        
        
        return [mmin, mmax, mean, median, mode]

All Problems

All Solutions