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:
count.length == 2561 <= sum(count) <= 10^9- The mode of the sample that count represents is unique.
- Answers within
10^-5of 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] -
func sampleStats(count []int) []float64 { find := func(i int) int { for k, t := 0, 0; ; k++ { t += count[k] if t >= i { return k } } } mi, mx := 1<<30, -1 s, cnt, mode := 0, 0, 0 for k, x := range count { if x > 0 { mi = min(mi, k) mx = max(mx, k) s += k * x cnt += x if x > count[mode] { mode = k } } } var median float64 if cnt&1 == 1 { median = float64(find(cnt/2 + 1)) } else { median = float64(find(cnt/2)+find(cnt/2+1)) / 2 } return []float64{float64(mi), float64(mx), float64(s) / float64(cnt), median, float64(mode)} } func min(a, b int) int { if a < b { return a } return b } func max(a, b int) int { if a > b { return a } return b } -
function sampleStats(count: number[]): number[] { const find = (i: number): number => { for (let k = 0, t = 0; ; ++k) { t += count[k]; if (t >= i) { return k; } } }; let mi = 1 << 30; let mx = -1; let [s, cnt, mode] = [0, 0, 0]; for (let k = 0; k < count.length; ++k) { if (count[k] > 0) { mi = Math.min(mi, k); mx = Math.max(mx, k); s += k * count[k]; cnt += count[k]; if (count[k] > count[mode]) { mode = k; } } } const median = cnt % 2 === 1 ? find((cnt >> 1) + 1) : (find(cnt >> 1) + find((cnt >> 1) + 1)) / 2; return [mi, mx, s / cnt, median, mode]; }