leetcode 1093. Statistics from a Large Sample

爱被打了一巴掌 2023-07-08 09:07 4阅读 0赞

[https://leetcode.com/problems/statistics-from-a-large-sample/][https_leetcode.com_problems_statistics-from-a-large-sample]

给定一个计数数组，其下标从0到255，计算其最小值、最大值、平均值、中位数、mode。

## 一、问题描述 ##

测试用例：

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]

## 二、代码实现 ##

用两轮遍历实现，一轮的做法可以参考下面的链接。

class Solution {
        public double[] sampleStats(int[] count) {
            int curMod = 0;
            
            double min = -1, max = -1, sum = 0, median = 0;
            
            int size = 0;
            for (int i=0; i<count.length; i++) {
                if (count[i] != 0) {
                    size += count[i];
                    if (min == -1) {
                        min = i;
                    }
                    max = i;
                    sum += count[i] * i;
                    if (count[i] > count[curMod]) {
                        curMod = i;
                    }
                }
            }
            
            int curNum = 0;        //当前访问到的数据个数
            int k = size / 2 + 1;    //当数据总数为奇数时为中位数；为偶数时为第二个中位数
            int lastNumber = 0;    //在遍历时记录当前访问数字的前一个数字（计数不为0）
            for (int i=0; i<count.length; i++) {
                if (count[i] != 0) {
                    curNum += count[i];
                    if (curNum < k) {
                        lastNumber = i;
                        continue;
                    } else {        //访问到中位数（奇数情况）或第二个中位数（偶数情况）
                        if (size%2 == 1) {
                            median = i;
                            break;
                        } else {
                            // if (curNum > k) {
                            //     median = i;
                            //     break;
                            // }
                            //System.out.println(size+"    "+k+"   "+curNum+"  "+(curNum-count[i]));
                            if (curNum == k || curNum - count[i] == k-1) {
                                median = (lastNumber + i) / 2.0;
                                break;
                            }
                            median = i;
                            break;
                        }
                    }
                }
            }
             
            return new double[] {min, max, sum*1.0/size, median, curMod};
        }
    }

参考：

[https://leetcode.com/problems/statistics-from-a-large-sample/discuss/318420/1-Pass-Solution][https_leetcode.com_problems_statistics-from-a-large-sample_discuss_318420_1-Pass-Solution]

[https://leetcode.com/problems/statistics-from-a-large-sample/discuss/317626/Python-Solution][https_leetcode.com_problems_statistics-from-a-large-sample_discuss_317626_Python-Solution]

[https://leetcode.com/problems/statistics-from-a-large-sample/discuss/317857/Java-Simple-2-pass-code-w-comments-and-explanation.][https_leetcode.com_problems_statistics-from-a-large-sample_discuss_317857_Java-Simple-2-pass-code-w-comments-and-explanation.]

[https://leetcode.com/problems/statistics-from-a-large-sample/discuss/323097/Java-1-Pass-two-pointer-solution][https_leetcode.com_problems_statistics-from-a-large-sample_discuss_323097_Java-1-Pass-two-pointer-solution]

[https_leetcode.com_problems_statistics-from-a-large-sample]: https://leetcode.com/problems/statistics-from-a-large-sample/
[https_leetcode.com_problems_statistics-from-a-large-sample_discuss_318420_1-Pass-Solution]: https://leetcode.com/problems/statistics-from-a-large-sample/discuss/318420/1-Pass-Solution
[https_leetcode.com_problems_statistics-from-a-large-sample_discuss_317626_Python-Solution]: https://leetcode.com/problems/statistics-from-a-large-sample/discuss/317626/Python-Solution
[https_leetcode.com_problems_statistics-from-a-large-sample_discuss_317857_Java-Simple-2-pass-code-w-comments-and-explanation.]: https://leetcode.com/problems/statistics-from-a-large-sample/discuss/317857/Java-Simple-2-pass-code-w-comments-and-explanation.
[https_leetcode.com_problems_statistics-from-a-large-sample_discuss_323097_Java-1-Pass-two-pointer-solution]: https://leetcode.com/problems/statistics-from-a-large-sample/discuss/323097/Java-1-Pass-two-pointer-solution