Google 新鲜面筋

tianlu1 发表于 2016-2-24 03:38
第一题O(n) non-sort解法：
keep four pointers: maximum_positive, second_max_positive, minimum_negati ...

两个数当然是这样了。。。楼主应该问的是K个数有没有比SORT更好的方法

googlerr 发表于 2016-2-26 11:45
应该是Queue里面只放K个元素，一个里面放最大的K个，另一个里面放最小的K个

priority queue?，两个priority queue，每次分别从两个HEAP里POP出两个，取最大乘积，一直到K个为止，如果K是奇数，最后那个只能取正的里面的，偶数就无所谓了

royal_916 发表于 2016-2-18 06:17
感觉第二题略难啊！祝lz onsite！

第二题是LC原题吧

sheepmiemies 发表于 2016-4-1 02:17
最大堆放负数那先取出来的岂不是-1,-2之类的绝对值小的数啊。。。。感觉这类题还是挺需要考虑全面的，比 ...

这里面有个矛盾其实，就是在更新的时候我们希望负数最大的先被POP出来，正数最小的先被POP出来，这样的话，我们就想负数用最大堆，正数用最小堆，但是最后在算乘积的时候就相反，这个矛盾感觉无法调和，我们最后在算乘积的时候另外用一个数据结构，比如LIST把堆里的数全部装起来，然后再算