題目
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.
題目大意
我們對 0 到 255 之間的整數進行採樣，並將結果存儲在數組 count 中：count[k] 就是整數 k 的採樣個數。
我們以 浮點數 數組的形式，分別返回樣本的最小值、最大值、平均值、中位數和眾數。其中，眾數是保證唯一的。我們先來回顧一下中位數的知識：
- 如果樣本中的元素有序，並且元素數量為奇數時，中位數為最中間的那個元素；
- 如果樣本中的元素有序，並且元素數量為偶數時，中位數為中間的兩個元素的平均值。
解題思路
- 這個問題的關鍵需要理解題目的意思，什麼是採樣？
count[k]就是整數k的採樣個數。 - 題目要求返回樣本的最小值、最大值、平均值、中位數和眾數。最大值和最小值就很好處理，只需要遍歷 count 判斷最小的非 0 的 index 就是最小值，最大的非 0 的 index 就是最大值。平均值也非常好處理，對於所有非 0 的 count，我們通過累加 count[k] * index 得到所有數的和，然後除上所有非 0 的 count 的和。
- 眾數也非常容易，只需統計 count 值最大時的 index 即可。
- 中位數的處理相對麻煩一些，因為需要分非 0 的 count 之和是奇數還是偶數兩種情況。先假設非 0 的 count 和為 cnt，那麼如果 cnt 是奇數的話，只需要找到 cnt/2 的位置即可，通過不斷累加 count 的值，直到累加和超過 ≥ cnt/2。如果 cnt 是偶數的話，需要找到 cnt/2 + 1 和 cnt/2 的位置，找法和奇數情況相同，不過需要找兩次(可以放到一個循環中做兩次判斷)。��次判斷)。
參考代碼
package leetcode
func sampleStats(count []int) []float64 {
res := make([]float64, 5)
res[0] = 255
sum := 0
for _, val := range count {
sum += val
}
left, right := sum/2, sum/2
if (sum % 2) == 0 {
right++
}
pre, mode := 0, 0
for i, val := range count {
if val > 0 {
if i < int(res[0]) {
res[0] = float64(i)
}
res[1] = float64(i)
}
res[2] += float64(i*val) / float64(sum)
if pre < left && pre+val >= left {
res[3] += float64(i) / 2.0
}
if pre < right && pre+val >= right {
res[3] += float64(i) / 2.0
}
pre += val
if val > mode {
mode = val
res[4] = float64(i)
}
}
return res
}