thumbtack 电面那个median题解法？

题意是给一个data stream 输入整数，输入的时候，可以随时调用getMedian()这个方法获得目前已输入数字的median。

听说是用一个bucket来存每个数的个数，但是最后怎么求median啊？

比如我有一个insert（）方法：

1. int[] nums = new int[1000];
   
2. public void insert(int num) {
   
3.         nums[num]++; // num becomes the index, value becomes the count for the num
   
4.       
   
5.     }
   
6.    
   
7.     public int getMedian() {
   
8.         // TODO: 这里需要遍历一遍那个NUMS 数组吗?咋求MEDIAN?
   
9.     }

复制代码

请大侠提供以下思路或代码？谢谢。。。。

edit: Deleted

你最好是说一下原题或者至少贴个链接，不然可能很多人并不知道你在说什么。

看你的代码的意思，是想从一个histogram中获得median。你只需从左向右遍历nums数组（其实叫freqs之类的更合适一点），同时计算nums的cumulative sum。一旦发现遍历到元素i时，cumulative sum超过了nums中所有元素和的一半。那就说明median肯定在这个bin中。如果bin的宽度只有1（即每个bin中只包含一个数字，比如你的示例代码中就是如此），那么这个数字就是median。如果bin的宽度超过1的话，你还需要用其他方法进一步在这个bin中再找meidan。另外，上面说的只是个大概原则。你可能还需要考虑median是两个不同数字的均值的情况。

stellari 发表于 2016-12-5 06:36
你最好是说一下原题或者至少贴个链接，不然可能很多人并不知道你在说什么。

看你的代码的意思，是想从一 ...

非常感谢，你的回复非常有帮助！

不好意思，问题有点过于简略。题意是给一个data stream 输入整数，输入的时候，可以随时调用getMedian()这个方法获得目前已输入数字的median。

我的code就是利用每个输入进去的数字作为数组的index，然后再更新这个index所对应的count。因为输入的数字的范围是1000以内。

再次感谢！

LC295,      

这题的意思是不能用heap么