Medium
题目描述
给你一个在范围 [0, 255] 内的整数的大样本。由于样本很大，用数组 count 表示，其中 count[k] 是 k 在样本中出现的次数。
计算以下统计量：
- minimum：样本中的最小元素。
- maximum：样本中的最大元素。
- mean：样本的平均值，计算为所有元素的总和除以元素总数。
- 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]。
最小值和最大值分别为 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.length == 256
- 0 <= count[i] <= 10^9
- 1 <= sum(count) <= 10^9
- count 所表示的样本的众数是唯一的。
解题思路
这道题目要求计算大样本的统计量，关键在于理解 count 数组的含义：count[i] 表示数字 i 在样本中出现的次数。
解题思路：
最小值和最大值：遍历 count 数组，找到第一个非零元素的索引作为最小值，最后一个非零元素的索引作为最大值。
平均值：计算总和除以总数量。总和 = Σ(i × count[i])，总数量 = Σcount[i]。
众数：遍历 count 数组，找到出现次数最多的数字。
中位数：这是最复杂的部分。需要找到排序后的第 n/2 和第 (n+1)/2 个元素（n为总元素个数）。
- 如果总数为奇数，中位数是第 (n+1)/2 个元素
- 如果总数为偶数，中位数是第 n/2 和第 n/2+1 个元素的平均值
对于中位数的计算，我们可以通过累加 count 数组来找到对应位置的元素。当累加和达到目标位置时，对应的索引就是我们要找的数字。
算法步骤：
- 一次遍历 count 数组，同时计算最小值、最大值、总和、总数量和众数
- 通过累加计数的方式找到中位数位置对应的元素值
- 根据总数量的奇偶性计算中位数
代码实现
class Solution {
public:
vector<double> sampleStats(vector<int>& count) {
int minimum = -1, maximum = -1, mode = 0;
long long sum = 0, total = 0;
int maxCount = 0;
// 一次遍历计算基本统计量
for (int i = 0; i < 256; i++) {
if (count[i] > 0) {
if (minimum == -1) minimum = i;
maximum = i;
sum += (long long)i * count[i];
total += count[i];
if (count[i] > maxCount) {
maxCount = count[i];
mode = i;
}
}
}
double mean = (double)sum / total;
// 计算中位数
double median;
if (total % 2 == 1) {
// 奇数个元素，找第 (total+1)/2 个元素
long long target = total / 2 + 1;
long long curr = 0;
for (int i = 0; i < 256; i++) {
curr += count[i];
if (curr >= target) {
median = i;
break;
}
}
} else {
// 偶数个元素，找第 total/2 和第 total/2+1 个元素
long long target1 = total / 2;
long long target2 = total / 2 + 1;
long long curr = 0;
int val1 = 0, val2 = 0;
for (int i = 0; i < 256; i++) {
curr += count[i];
if (curr >= target1 && val1 == 0) val1 = i;
if (curr >= target2) {
val2 = i;
break;
}
}
median = (val1 + val2) / 2.0;
}
return {(double)minimum, (double)maximum, mean, median, (double)mode};
}
};
class Solution:
def sampleStats(self, count: List[int]) -> List[float]:
minimum = maximum = mode = -1
total_sum = total_count = max_count = 0
# 一次遍历计算基本统计量
for i in range(256):
if count[i] > 0:
if minimum == -1:
minimum = i
maximum = i
total_sum += i * count[i]
total_count += count[i]
if count[i] > max_count:
max_count = count[i]
mode = i
mean = total_sum / total_count
# 计算中位数
if total_count % 2 == 1:
# 奇数个元素，找第 (total_count+1)/2 个元素
target = total_count // 2 + 1
curr = 0
for i in range(256):
curr += count[i]
if curr >= target:
median = float(i)
break
else:
# 偶数个元素，找第 total_count/2 和第 total_count/2+1 个元素
target1 = total_count // 2
target2 = total_count // 2 + 1
curr = 0
val1 = val2 = 0
for i in range(256):
curr += count[i]
if curr >= target1 and val1 == 0:
val1 = i
if curr >= target2:
val2 = i
break
median = (val1 + val2) / 2.0
return [float(minimum), float(maximum), mean, median, float(mode)]
public class Solution {
public double[] SampleStats(int[] count) {
int minimum = -1, maximum = -1, mode = 0;
long sum = 0, total = 0;
int maxCount = 0;
// 一次遍历计算基本统计量
for (int i = 0; i < 256; i++) {
if (count[i] > 0) {
if (minimum == -1) minimum = i;
maximum = i;
sum += (long)i * count[i];
total += count[i];
if (count[i] > maxCount) {
maxCount = count[i];
mode = i;
}
}
}
double mean = (double)sum / total;
// 计算中位数
double median;
if (total % 2 == 1) {
// 奇数个元素，找第 (total+1)/2 个元素
long target = total / 2 + 1;
long curr = 0;
for (int i = 0; i < 256; i++) {
curr += count[i];
if (curr >= target) {
median = i;
break;
}
}
} else {
// 偶数个元素，找第 total/2 和第 total/2+1 个元素
long target1 = total / 2;
long target2 = total / 2 + 1;
long curr = 0;
int val1 = 0, val2 = 0;
for (int i = 0; i < 256; i++) {
curr += count[i];
if (curr >= target1 && val1 == 0) val1 = i;
if (curr >= target2) {
val2 = i;
break;
}
}
median = (val1 + val2) / 2.0;
}
return new double[] { minimum, maximum, mean, median, mode };
}
}
/**
* @param {number[]} count
* @return {number[]}
*/
var sampleStats = function(count) {
let min = -1, max = -1;
let total = 0, sum = 0;
let maxCount = 0, mode = 0;
// Find min, max, total count, sum, and mode
for (let i = 0; i < 256; i++) {
if (count[i] > 0) {
if (min === -1) min = i;
max = i;
total += count[i];
sum += i * count[i];
if (count[i] > maxCount) {
maxCount = count[i];
mode = i;
}
}
}
let mean = sum / total;
// Find median
let median;
let mid1 = Math.floor((total - 1) / 2);
let mid2 = Math.floor(total / 2);
let currCount = 0;
let median1 = -1, median2 = -1;
for (let i = 0; i < 256; i++) {
if (count[i] > 0) {
let nextCount = currCount + count[i];
if (median1 === -1 && mid1 < nextCount) {
median1 = i;
}
if (median2 === -1 && mid2 < nextCount) {
median2 = i;
}
if (median1 !== -1 && median2 !== -1) break;
currCount = nextCount;
}
}
median = (median1 + median2) / 2;
return [min, max, mean, median, mode];
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(1) |
| 空间复杂度 | O(1) |
说明：
- 时间复杂度：O(1)，因为数组长度固定为 256，所以遍历次数是常数
- 空间复杂度：O(1)，只使用了常数个额外变量