Google 新鲜面筋

csgtc 发表于 2016-2-26 08:13
两个priorityqueue， 复杂度并不是sort的nlogn，而是nlogk 速度肯定比sort快

nlogk如何得来？我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k)复杂度 总共是nlogn 能说说你的思路吗？

hesha0987 发表于 2016-2-26 11:42
nlogk如何得来？我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k) ...

应该是Queue里面只放K个元素，一个里面放最大的K个，另一个里面放最小的K个

第一题可以sort吗？最大乘积就是Max（最小两个负数乘积，最大两个正数乘积）

tianlu1 发表于 2016-2-27 00:07
第一题可以sort吗？最大乘积就是Max（最小两个负数乘积，最大两个正数乘积）

忘了以前回复过，参看地板楼，忽略此楼

hesha0987 发表于 2016-2-25 22:42
nlogk如何得来？我有点没明白。。我想的是把n个元素放入priority_queue 为nlogn复杂度 然后pop k次为O(k) ...

恩queue里只有k个元素，没必要把所有元素放queue里啊，所有元素放queue里就是heapsort了

csgtc 发表于 2016-2-27 03:09
恩queue里只有k个元素，没必要把所有元素放queue里啊，所有元素放queue里就是heapsort了

明白了 然后每次pop出一个来 多谢！

unique word abbreviation 是啥？

csgtc 发表于 2016-2-27 03:09
恩queue里只有k个元素，没必要把所有元素放queue里啊，所有元素放queue里就是heapsort了

queue里面只有k 个元素，那当k+1个元素进来，如何删除最小的那个呢（假设是个max heap）？

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

为什么需要存second？直接存最大值会有什么问题么？one pass， 如果小于0，与最小负数乘法，然后更新最大值，如果大于0和最大正数乘法，然后更新最大值。

未命名0Zero 发表于 2016-3-4 03:37
queue里面只有k 个元素，那当k+1个元素进来，如何删除最小的那个呢（假设是个max heap）？

Heap里面要存的是最大的K个元素，所以用Min Heap更好外带加一个max标记heap里面最大值。当加满K个元素的时候，如果当前的元素大于Heap里面最小的值，删除当前最小的，然后加当前的，同时更新max如果有必要