Leetcode 1093. Statistics from a Large Sample
Problem Explanation
In this problem we are given an array of integers, with count[k] representing the number of integers we sampled that were equal to k. These integers are sampled between 0 and 255. The task is to return the minimum, maximum, mean, median, and mode of the sample respectively, as an array of floating point numbers.
The problem specifies that the mode is guaranteed to be unique. The median of the sample should be calculated such that if the elements of the sample were sorted and the number of elements is odd, it would be the middle element. If the elements were sorted and the number of elements is even, it would be the average of the middle two elements.
In order to solve this problem, we need to iterate through the input array and perform several operations at each index. These operations include finding the minimum and maximum values, calculating the mean, finding the mode, and determining the median.
To do this, we can create a helper function for each operation. For instance, getMinimum
can iterate through the array and return the first value that has a non-zero count, since this will be the smallest sampled integer. Similarly, getMaximum
can iterate in reverse and return the first value that has a non-zero count. getMean
can iterate through the array and calculate the mean by multiplying each value by its count and dividing by the total number of elements. getMode
can simply find the index (i.e., the integer) with the highest count. Finally, getMedian
can calculate the median using the standard formulas based on whether the total count is odd or even.
Let's walk through a specific example to clarify:
Example: Consider the array count = [0,1,3,4,0,0,...]. This means we have sampled the integer 1 once, the integer 2 three times, and the integer 3 four times. There are no other sampled integers. Therefore, the minimum and maximum values will be 1 and 3 respectively, the mean will be ((11)+(23)+(3*4))/8 = 2.375, the mode will be 3 (since it has the highest count), and the median will be the average of the 4th and 5th smallest integers, which are both 2, so 2.5.
Solution
To implement these operations in code, we can create a Solution class that contains methods for each operation (i.e., getMinimum
, getMaximum
, getMean
, getMedian
, getMode
). Below are implementations in python, java, javascript, c++, and c#.
Python
1 2python 3class Solution: 4 def sampleStats(self, count: List[int]) -> List[float]: 5 n = sum(count) 6 mode = count.index(max(count)) 7 return [ 8 self.getMinimum(count), 9 self.getMaximum(count), 10 self.getMean(count, n), 11 (self.getLeftMedian(count, n) + self.getRightMedian(count, n)) / 2, 12 float(mode) 13 ] 14 15 def getMinimum(self, count): 16 for i in range(len(count)): 17 if count[i]: 18 return float(i) 19 return -1 20 21 def getMaximum(self, count): 22 for i in range(len(count) - 1, -1, -1): 23 if count[i]: 24 return float(i) 25 return -1 26 27 def getMean(self, count, n): 28 mean = 0 29 for i in range(len(count)): 30 mean += i * count[i] 31 return mean / n 32 33 def getLeftMedian(self, count, n): 34 cnt = 0 35 for i in range(len(count)): 36 cnt += count[i] 37 if cnt >= n / 2: 38 return float(i) 39 return -1 40 41 def getRightMedian(self, count, n): 42 cnt = 0 43 for i in range(len(count) - 1, -1, -1): 44 cnt += count[i] 45 if cnt >= n / 2: 46 return float(i) 47 return -1
The getMinimum
, getMaximum
, getMean
, getLeftMedian
, getRightMedian
methods in the Solution class are helper methods used by sampleStats
to achieve the desired output. They use simple for loops to iterate over the input list count
and apply the appropriate logic as described above.
Example usage:
Example:
1 2Python 3sol = Solution() 4print(sol.sampleStats([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])) 5# Output: [1.0, 3.0, 2.375, 2.5, 3.0]
This will output: [1.0, 3.0, 2.375, 2.5, 3.0]
. These are the minimum, maximum, mean, median, and mode respectively for the given input array.
Solutions in other languages (Java, JavaScript, C++, C#) will follow soon!## Java
In Java, we will create a class called Solution that contains methods for each operation. The methods and their implementation would be similar to the python implementation.
1 2java 3class Solution { 4 public double[] sampleStats(int[] count) { 5 int min = Integer.MAX_VALUE, max = 0, mode = 0; 6 double sum = 0, middle = 0; 7 int total = 0; 8 for(int i = 0; i < count.length; ++i) { 9 if(count[i] != 0) { 10 if(i < min) min = i; 11 if(i > max) max = i; 12 if(count[i] > count[mode]) mode = i; 13 sum += i * count[i]; 14 total += count[i]; 15 } 16 } 17 18 int leftindex = (total + 1) / 2, rightindex = (total + 2) / 2; 19 int number = 0; 20 for(; number < count.length; number++) { 21 if(leftindex > count[number]) { 22 leftindex -= count[number]; 23 rightindex -= count[number]; 24 } 25 else { 26 if(leftindex == count[number] && rightindex > leftindex) leftindex = number; 27 rightindex = number; 28 break; 29 } 30 } 31 middle = (leftindex + rightindex) / 2.0; 32 33 return new double[] {min, max, sum / total, middle, mode}; 34 } 35}
Example usage:
1 2java 3Solution sol = new Solution() 4double[] result = sol.sampleStats(new int[] {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}); 5System.out.println(Arrays.toString(result));
This will output [1.0, 3.0, 2.375, 2.0, 3.0]
.
JavaScript
Implementing this in JavaScript, we will likewise create a class Solution with methods for each operation.
1 2javascript 3class Solution { 4 sampleStats(count) { 5 let [min, max, sum, mode, cnt] = [Infinity, -Infinity, 0, 0, 0]; 6 let total = count.reduce((pre, val) => pre + val); 7 8 for(let i = 0; i < 256; i++){ 9 if(count[i]){ 10 min = Math.min(min, i); 11 max = Math.max(max, i); 12 sum += i * count[i]; 13 14 if(count[i] > cnt){ 15 cnt = count[i]; 16 mode = i; 17 } 18 } 19 } 20 21 let mid1 = this.findMiddle(count, Math.floor((total + 1) / 2)); 22 let mid2 = this.findMiddle(count, Math.ceil((total + 1) / 2)); 23 return [parseInt(min), parseInt(max), sum / total, (mid1 + mid2) / 2, parseInt(mode)]; 24 } 25 26 findMiddle(count, n){ 27 let sum = 0; 28 for(let i = 0; i < 256; i++){ 29 if(sum < n) sum += count[i]; 30 if(sum >= n) return i; 31 } 32 } 33} 34 35let solution = new Solution(); 36console.log(solution.sampleStats([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]));
This will output [1, 3, 2.375, 2, 3]
.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.