f*******r
发帖数: 1086 | 1 自己刚刚写了一下O(n^2)的算法，还没想明白
O(nlogk)的算法的思想，哪位大侠麻烦赐教一下，
非常感谢！ |
|
a**q
发帖数: 3 | 2 假设一共有n个节点。我说复杂度是nlogk，但是面试官说复杂度就是n。我问他为什么
，他说因为是建堆，堆不是完全排好序的，所以不用logk用1就可以了。我当时比划了
两下还是觉得应该是logk，但是因为面试时间有限就没有当场深究。现在又想了一下，
确实应该是nlogk而不是n，一个特例是假设k=n，那么就相当于排序，复杂度nlogn。我
该怎么办呢？是发邮件告诉面试官应该是nlogk还是坐以待毙？ |
|
l******i
发帖数: 880 | 3 我一直觉得是nlogk啊。。。堆调整不是logk吗？一共n次，所以nlogk?
我看到一种说法是求最大K个，用最大堆的话是klogn，用最小堆是nlogk? |
|
D***h
发帖数: 183 | 4 用heap就是O(nlogk)
一般不明确说明的话，都是指最坏情况的。
我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
Time Complexity measures分 Best, worst and average
用具体操作的布数来衡量
Big O 给了一个 Upper and lower bounds on the complexity
所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
例如：k个最大数问题
最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
；最坏，arr从小到大排序，heap需要调整，步骤 n + n*logk
用big O的话是O(nlogk) <--这个还是不确定到底对不对 |
|
n*******n
发帖数: 3 | 5 我来试着证明一下本题的时间复杂度是有下限的。而且下限是 O(nlogk)， n为所有
integer的个数. 证明如下：
一般常识是sort n个integer最快是O(nlogn). 所以把n个integer分成k组，每组分别
sort，再合起来，不可能比O(nlogn)更快。 n ＝ k * m
分别sort k 个 size 为 m的数组共需时间 k * O(mlogm) = O(nlogm). 所以merge k个
数组的时间不可能小于 O（nlogn）- O(nlogm) = O(nlog(n/m)) = O(nlogk) .
楼上各位已经找到最优解了。 |
|
d********r
发帖数: 38 | 6 NLogK, N is the total number of elements in K lists
Merging two lists with length N1 and N2 is O(N1+N2)
So the first round of k/2 merges totally took O(N) time
So as the second round, etc.
The total number of rounds is LogK, so O(NlogK). |
|
j*********6
发帖数: 407 | 7 用priority queue的话， running time 是 k+nlogk 吧， 其实就是O(nlogk) 因为你
就是top k 的问题 然后 override一下comparator的compare 函数 只比较 绝对值就
行了
我觉得这个online test 分析 也是很重要的 因为题目不难 很多人都能做出来 所以
就看谁的分析更好 code 更clean
加油！！ |
|
k******e
发帖数: 19 | 8
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
k******e
发帖数: 19 | 9
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
h***k
发帖数: 161 | 10 第二个为什么不是O(NlogK)呢？
我的想法是先hashmap把所有words数一遍，O(N) memory+time, 然后用k-size的
minheap遍历hashmap,总共是O(NlogK)。 |
|
b*******8
发帖数: 37364 | 11 这个小蒙古最会了，K个元素用堆，替换是对数时间，整个开销NlogK |
|
r**u
发帖数: 1567 | 12 Given a set S of n distinct numbers and a positive integer k <= n. Determine
the k numbers in S that are closest to the median of S. Find an O(n)
algorithm.
这个就是先找到median，然后搞个max heap，每个数都有个到median的distance, 如果
小于heap顶，放到heap，O(nlogk)。对不？ |
|
g*******y
发帖数: 1930 | 13 达不到要求
题目说的是O(n)
而k是小于等于n的数
O(nlogk) = O(nlogn)
其实可以这样：
找到median后，对于每个数，算一个新的数组b[i] = abs(a[i]-median)
然后在b[i]中找k-th元素，然后再遍历一遍就可以找到k个最小的了。
这样保证是O(n)
这个题告诉我们，heap也不是万金油，呵呵 |
|
c****s
发帖数: 241 | 14 我感觉计算了distance之后，维持一个k大小的heap。这样可以做到O(nlogk)。
应该不会有更快的了吧？您老还有什么更好的方法？ |
|
B*****t
发帖数: 335 | 15 可以做到只比较N+logN+loglogN+...(一共有k项）次， 当k接近N/2时，显然要比nlogk
的算法快， 缺点是可能要多一点儿的空间， 不过也不一定。 |
|
l*****a
发帖数: 14598 | 16 where does K come from? |
|
f*******r
发帖数: 1086 | 17 也可以说是nLog(n) 吧，我是看到有文章提到k表示子序列的长度 |
|
|
f*******r
发帖数: 1086 | 19 非常感谢，不过刚看了一下还是没有清晰的思路，
能简单地描述一下思想吗？谢谢了！ |
|
|
c*********7
发帖数: 19373 | 21 也提出个问题，如果每次都是从上次结束的位置开始岂不是到O(n).比如第一个
increasing 是从1到k1,然后下个搜索从k1+1开始。 |
|
l******o
发帖数: 144 | 22 如果wiki都不能让你理解的话，我们可能也很难了。
非常感谢，不过刚看了一下还是没有清晰的思路，
能简单地描述一下思想吗？谢谢了！ |
|
x****r
发帖数: 99 | 23 wiki里面那个还稍微麻烦了，他那样是可以retrieve这个sequence的方法，如果只需要
长度，可以这样做
数组a[i]里面可以存长度为i的子序列，最小的结尾是多少
基本是这样
数组： 99 100 100 1 2 3 4
第1步. 99 ：binary search 最大一个<=99的，没有，所以a[1] = 99;
第2步. 100 ：binary search 最大一个<=100的，就是a[1]， 所以a[2] = 100;（意
思是现在长度为2的不减数列最少是100结尾）
第3步. 100 ：binary search 最大一个<=100的，是a[2]，所以a[3] = 100;
第4步. 1 : binary search 最大一个<=1的，没有，所以a[1] = 1;
第5步. 2 : binary search 最大一个<=2的，是a[1],所以A[2] = 2；
第6步. 同上，设置a[3] = 3;
第7步. 同上, 设置a[4] = 4;
至此，取得最大的a的index，就是4，所以长度最长的不减小子串是4，不知道讲明白了
没有 |
|
y**i
发帖数: 1112 | 24 你这个情况如果数组是99 100 100 1 2呢，最后不是到a[2] = 2就停止了，最大index
= 2了？ |
|
x****r
发帖数: 99 | 25 不是的，因为看到第三个100的时候，最大length已经被设置为3了，所以最后还是返回
3，返回的值是
这个数组里index最大的一个非空的值
index |
|
K******g
发帖数: 1870 | 26 不懂。
首先，binary search整个数组吗？比如说“binary search 最大一个<=99的”， 为什
么“没有”，如果是搜索这个数组，难道99不是吗？如果是搜索剩余的数组，难道4不
是吗？
为什么到第4步的时候，就回到“a【1】”去了？
非常confusing |
|
|
B*****t
发帖数: 335 | 28 可以用堆来做，复杂度O(nlogk)
这题overlapping 的subproblems不好定义，DP好像不是很适合
smallest window
you know
have a list
propose an |
|
c*********7
发帖数: 19373 | 29 不是用heap?k space。这个如果只是数组或stream数据的话应该是用heap。换成矩阵应
该也是吧O(nlogk)。也有人提过用quicksort的方法来做，但不一定能保证每次都能找
到最优piviot。 |
|
g*****u
发帖数: 298 | 30 这个复杂度我觉得不能做到O(n)，因为还要看k
我觉得是O(nlogk) |
|
f****4
发帖数: 1359 | 31 我知道我把哪搞混了，我写一下，有错的话，请指出来，谢谢
Time Complexity measures分 Best, worst and average
用具体操作的布数来衡量
Big O 给了一个 Upper and lower bounds on the complexity
所以，如果给问到Time Complexity就的列出在那种衡量方法下的布数之和
例如：k个最大数问题
最优，arr从大到小排序，heap不需要进行调整，前k个就是答案；所以操作步骤是n步
；最坏，arr从小到大排序，heap需要调整，步骤 n + n*logk
用big O的话是O(nlogk) <--这个还是不确定到底对不对 |
|
D***h
发帖数: 183 | 32 建大小为k的堆，每次操作是logk, n个元素，所以总共是O(nlogk). |
|
h**k
发帖数: 3368 | 33
klgn)
用min heap的复杂度是O(nlogk),heap的大小是k，一共插入n个元素。
用binary search的思路可以实现O(n+k)
可以的，需要改一下算法。 |
|
f*********5
发帖数: 576 | 34 来自主题: JobHunting版 - 一道电面题 if u think so,that is fine.
but when we talk about time complexity,we will definitely choose
nlogk ,while not nlogn.
sure,we will use O(k) for extra space while u don't need.
at least we should mention this to the interviewer
50000*16 |
|
p******r
发帖数: 2999 | 35 明显是因为实时嘛
如果k-th小的话，O(nlogk)也不错 |
|
j*****u
发帖数: 1133 | 36 写了个只返回count的，要返回子序列在这个基础上加一个index array就可以了。
time O(nlogk), space O(k), k == length of LIS
int LIS(int[] array)
{
if (array == null || array.Length == 0)
return 0;
var incIndex = new List { 0 };
for (int i = 1; i < array.Length; ++i)
{
if (array[i] > array[incIndex.Last()])
incIndex.Add(i);
else
{
int l = 0;
for (int r = incIndex.Count; l <= r;)
{
int m = l + (r - l) / 2;
... 阅读全帖 |
|
j*****u
发帖数: 1133 | 37 这是很经典的DP问题，但我只知道O(nlogk)的解。 |
|
F**********r
发帖数: 237 | 38 这回这个问题可能和具体实现有关，就是k-way merge。
1）首先如果能够全部load进内存，是不是其实最好就是依序把它们放进连续内存，然
后直接sort。O(nlogn)
如果用heap的话，要么就是heap的每个element要有data+index（2.1),要么就是要有一
个size k的array存放每个array的active index,但是要决定具体要advance which
array的时候，worst case要把size k array所指向的element和heap top比较一次(2.2
)：这本身复杂度就是k*n了。。。。另外虽然heap move down直接成堆复杂度是O(n),
但并不适用在这个case。也就是说用堆的话复杂度是O（nlogk)+ 更多内存 或者 O(n*k
).
这个理解对么？大家怎么看？ |
|
w********n
发帖数: 13 | 39 the little tricky function is the recursive function, where u need to
determine when to stop partition so that u can achieve Nlogk
one thing to do is to keep a variable in this partition to determine whether
this partition only contains 1 color. |
|
w**7
发帖数: 71 | 40 面试加州P公司
一面是华人GG
1. 给个数组，给个target, 求找两个数和等于target
然后拓展到找3个数，4个数，分析复杂度
这经典题，没啥说的，hashmap
一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
这个用hashmap存层数和路径长度值，从底层向上遍历
二面是个白人
2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
数组排序
这就是弄个k size 的min-maxheap, 然后先把前0-k-1个元素放到heap里，然后从数组K
位置开始，从heap中取出最小，然后从数组取一个放到heap里，最后O(nlogk)排好
我把方法一说，interviewer感觉可以，说那你写个code发过来吧，然后do you have
any questions。没20分钟就结束了
两面感觉都没啥问题，最后周一就收thank you letter了。有好几次都这样，感觉
technical 题目都没啥问题，两面就悲剧，求经验……move on到麻木了，唉 |
|
a*********0
发帖数: 2727 | 41 it's still n-way merge with the aid of min-heap. O(nlogk)complexity |
|
f**********t
发帖数: 1001 | 42 对。
Min-heap O(nlogk)
method 2那个O(nk) |
|
s***h
发帖数: 662 | 43 贡献一点面经.
我准备的时间还不够, 今天这二面有点忐忑.面我的人是个白人小伙子, 说话很快, 不
停的提附加问题.
1. how to pick first k maximum numbers in an array.
me: most straightforward, sort then pick, nlgn + k
he: ok...
me: better way, quick select, n * k
he: what is quick select, why is it linear time?
me: talking...
he: what if array is way bigger than the memory, can this work?
me:...yes...but slower due to swapping...
he: anything better?
me: ...
我不太明白他想问什么,所以没答上这一问,最后他问我有什么问题的时候我就
问了他,他说,你可以构造一个size k heap. then it is nlogk. 哎, 我当时真
没往... 阅读全帖 |
|
r*******h
发帖数: 315 | 44 你没有理解min heap和max heap的特点,而且建堆也是要时间的，用max heap，保持heap大小为
k，利用删除堆最大元素只要lgn的特点，所以找第k小只要nlogk，如果你用min heap同样的做法，
最后留下的是最大的k个数，或者你得借助min heap来一次排序，那就跟quick sort一样
最后要nlogn. |
|
w****m
发帖数: 146 | 45 Get your point
ps：建堆是线性的，所以用minheap的话，remove root k次，复杂度是o(n+klogn),这个和
o(k+nlogk)比很难说那个比较快吧？
heap大小为
同样的做法，
一样 |
|
H****s
发帖数: 247 | 46 为啥要用heap 呢？占用额外空间。 直接排序前2k个前k个就是排好序的，然后再加上接下来的k个形
成2k个再排序，直到最后 O(Nlogk) |
|
d**0
发帖数: 124 | 47 请教一个题目： k个unsorted arrays，假设都是n个元素。怎么样快速求出median？
不能把所有的array拼到一起再做quick selection。
我用类似quick selection的方法使用同一个pivot element在k个arrays里quick
select，再求
方法应该是这样，但是复杂度分析不出来。一个naive的bound是o(kn),但是这样就和拼
到一起做quick select一样。最后猜了一个o(nlogk)但是自己也不是很信服。
请大牛指教，谢谢！ |
|
|
f*******n
发帖数: 12623 | 49 的确是nlogk。O(1)可以拿到top element，但是要remove它，还是要O(log k)。
假如k=n，那按照他说的就可以用这个方法O(n)去sort一个unsorted的array了。 |
|
w****x
发帖数: 2483 | 50 nlogk, 怎么会是O(n),
不过现实当中我觉得merge k array用堆不一定比不用直接比较的O(n*k)快, 甚至更慢 |
|
