class Solution {
public:
vector<double> sampleStats(vector<int>& count) {
}
};
1093. 大样本统计
我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 在样本中出现的次数。
计算以下统计数据:
minimum ：样本中的最小元素。maximum ：样品中的最大元素。mean ：样本的平均值，计算为所有元素的总和除以元素总数。median ：
median 就是中间的元素。median 就是样本排序后中间两个元素的平均值。mode ：样本中出现次数最多的数字。保众数是 唯一 的。以浮点数数组的形式返回样本的统计信息 [minimum, maximum, mean, median, mode] 。与真实答案误差在 10-5 内的答案都可以通过。
示例 1：
输入：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] 输出：[1.00000,3.00000,2.37500,2.50000,3.00000] 解释：用count表示的样本为[1,2,2,2,3,3,3,3,3]。 最小值和最大值分别为1和3。 均值是(1+2+2+2+3+3+3+3) / 8 = 19 / 8 = 2.375。 因为样本的大小是偶数，所以中位数是中间两个元素2和3的平均值，也就是2.5。 众数为3，因为它在样本中出现的次数最多。
示例 2：
输入：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] 输出：[1.00000,4.00000,2.18182,2.00000,1.00000] 解释：用count表示的样本为[1,1,1,1,2,2,3,3,3,4,4]。 最小值为1，最大值为4。 平均数是(1+1+1+1+2+2+2+3+3+4+4)/ 11 = 24 / 11 = 2.18181818…(为了显示，输出显示了整数2.18182)。 因为样本的大小是奇数，所以中值是中间元素2。 众数为1，因为它在样本中出现的次数最多。
提示：
count.length == 2560 <= count[i] <= 1091 <= sum(count) <= 109count 的众数是 唯一 的原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-05-27 22:42:54
func sampleStats(count []int) []float64 {
n := len(count)
total := 0
for i := 0; i < n; i++ {
total += count[i]
}
mean := 0.0
median := 0.0
minimum := 256
maxnum := 0
mode := 0
left := (total + 1) / 2
right := (total + 2) / 2
cnt := 0
maxfreq := 0
sum := 0
for i := 0; i < n; i++ {
sum += int(count[i]) * int(i)
if count[i] > maxfreq {
maxfreq = count[i]
mode = i
}
if count[i] > 0 {
if minimum == 256 {
minimum = i
}
maxnum = i
}
if cnt < right && cnt+count[i] >= right {
median += float64(i)
}
if cnt < left && cnt+count[i] >= left {
median += float64(i)
}
cnt += count[i]
}
mean = float64(sum) / float64(total)
median = median / 2.0
return []float64{float64(minimum), float64(maxnum), mean, median, float64(mode)}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-27 22:42:38
class Solution:
def sampleStats(self, count: List[int]) -> List[float]:
n = len(count)
total = sum(count)
mean = 0.0
median = 0.0
min_num = 256
max_num = 0
mode = 0
left = (total + 1) // 2
right = (total + 2) // 2
cnt = 0
max_freq = 0
sum_ = 0
for i in range(n):
sum_ += count[i] * i
if count[i] > max_freq:
max_freq = count[i]
mode = i
if count[i] > 0:
if min_num == 256:
min_num = i
max_num = i
if cnt < right and cnt + count[i] >= right:
median += i
if cnt < left and cnt + count[i] >= left:
median += i
cnt += count[i]
mean = sum_ / total
median = median / 2.0
return [min_num, max_num, mean, median, mode]
golang 解法, 执行用时: 4 ms, 内存消耗: 2.5 MB, 提交时间: 2023-05-27 22:42:10
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
}
java 解法, 执行用时: 1 ms, 内存消耗: 41.8 MB, 提交时间: 2023-05-27 22:41:44
class Solution {
private int[] count;
public double[] sampleStats(int[] count) {
this.count = count;
int mi = 1 << 30, mx = -1;
long s = 0;
int cnt = 0;
int mode = 0;
for (int k = 0; k < count.length; ++k) {
if (count[k] > 0) {
mi = Math.min(mi, k);
mx = Math.max(mx, k);
s += 1L * k * count[k];
cnt += count[k];
if (count[k] > count[mode]) {
mode = k;
}
}
}
double median = cnt % 2 == 1 ? find(cnt / 2 + 1) : (find(cnt / 2) + find(cnt / 2 + 1)) / 2.0;
return new double[]{mi, mx, s * 1.0 / cnt, median, mode};
}
private int find(int i) {
for (int k = 0, t = 0;; ++k) {
t += count[k];
if (t >= i) {
return k;
}
}
}
}
python3 解法, 执行用时: 32 ms, 内存消耗: 16.2 MB, 提交时间: 2023-05-27 22:41:27
class Solution:
def sampleStats(self, count: List[int]) -> List[float]:
def find(i: int) -> int:
t = 0
for k, x in enumerate(count):
t += x
if t >= i:
return k
mi, mx = inf, -1
s = cnt = 0
mode = 0
for k, x in enumerate(count):
if x:
mi = min(mi, k)
mx = max(mx, k)
s += k * x
cnt += x
if x > count[mode]:
mode = k
median = find(cnt // 2 + 1) if cnt & 1 else (find(cnt // 2) + find(cnt // 2 + 1)) / 2
return [mi, mx, s / cnt, median, mode]