[LeetCode] Statistics from a Large Sample

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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};
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/07/05/PS/LeetCode/statistics-from-a-large-sample/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.