1093. Statistics from a Large Sample #

Problem #

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]
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]
Output: [1.00000,4.00000,2.18182,2.00000,1.00000]

Constraints:

count.length == 256
1 <= sum(count) <= 10^9
The mode of the sample that count represents is unique.
Answers within 10^-5 of the true value will be accepted as correct.

Problem Summary #

We sample integers between 0 and 255, and store the results in the array count: count[k] is the number of samples of integer 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. First, let’s review the definition of the median:

If the elements in the sample are sorted and the number of elements is odd, the median is the middle element;
If the elements in the sample are sorted and the number of elements is even, the median is the average of the two middle elements.

Solution Approach #

The key to this problem is understanding what the problem means. What is sampling? count[k] is the number of samples of integer k.
The problem asks us to return the minimum, maximum, mean, median, and mode of the sample. The maximum and minimum are easy to handle: just traverse count and determine that the smallest non-zero index is the minimum value, and the largest non-zero index is the maximum value. The mean is also very easy to handle. For all non-zero counts, we accumulate count[k] * index to get the sum of all numbers, then divide by the sum of all non-zero counts. \[ \sum_{n=0}^{256}count[n],count[n]!=0 \]
The mode is also very easy: just record the index when the count value is the largest.
Handling the median is relatively more troublesome, because we need to distinguish between two cases: whether the sum of non-zero counts is odd or even. First assume the sum of non-zero counts is cnt. If cnt is odd, we only need to find the position cnt/2 by continuously accumulating the count values until the cumulative sum reaches ≥ cnt/2. If cnt is even, we need to find the positions cnt/2 + 1 and cnt/2. The search method is the same as in the odd case, except that we need to search twice (the two checks can be done in one loop).

Code #


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
}