an interview question# Programming - 葵花宝典
i*y
1 楼
a. Given an array of n integers, can you write an algorithm that finds k
smallest numbers?
b. What is the complexity of your algorithm?
smallest numbers?
b. What is the complexity of your algorithm?
t*l
2 楼
能想到最好的办法就是建立一个k-element的max-heap.复杂度是O(nlogk)
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
s*u
3 楼
k smallest numbers是nth_element的副产品
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
j*g
4 楼
same idea as quick sort.
Use a pivot p as comparison base. All numbers larger than p move to right,
smaller move to left. Recurse on either left side with (k) or right side
with (k - #Worst case is n^2.
No time for average case, but I guess should be O(n).
Use a pivot p as comparison base. All numbers larger than p move to right,
smaller move to left. Recurse on either left side with (k) or right side
with (k - #Worst case is n^2.
No time for average case, but I guess should be O(n).
N*n
5 楼
A max-heap solution is faster than that.
【在 s****u 的大作中提到】
: k smallest numbers是nth_element的副产品
:
: k
【在 s****u 的大作中提到】
: k smallest numbers是nth_element的副产品
:
: k
p*n
6 楼
why?
【在 N********n 的大作中提到】
: A max-heap solution is faster than that.
【在 N********n 的大作中提到】
: A max-heap solution is faster than that.
e*w
7 楼
O(N) time to select the k-th smallest element X. (see CLRS)
O(N) time to scan the array and compare with X to get the k smallest numbers.
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
O(N) time to scan the array and compare with X to get the k smallest numbers.
k
【在 i*****y 的大作中提到】
: a. Given an array of n integers, can you write an algorithm that finds k
: smallest numbers?
: b. What is the complexity of your algorithm?
e*e
8 楼
第一步的副产品不就是答案了么？
numbers.
【在 e*****w 的大作中提到】
: O(N) time to select the k-th smallest element X. (see CLRS)
: O(N) time to scan the array and compare with X to get the k smallest numbers.
:
: k
numbers.
【在 e*****w 的大作中提到】
: O(N) time to select the k-th smallest element X. (see CLRS)
: O(N) time to scan the array and compare with X to get the k smallest numbers.
:
: k
相关阅读
Linux/C++的工作好难找真佩服你们，VS6和VC能吵一晚上求问：游戏中比较自然的路径寻找算法有啥简单方案？cross origin resource sharing有Reddit帐号的帮忙去顶一下啊问一个简单C++问题python哪个JSON库最好？FMP supports UI thread in both Swing and SWTDao语言2.0第一个测试版发布了！湾区的啥时候一起吃个饭吧这个新闻大概表明云平台在数据安全方面没有太大问题吧？c++ primer 和 c++ programming language 这两本书有什么区别写thread safe程序现在也是程序员必须要掌握的了吧问个随机数的问题学了一个星期linux内核，顿感人生层次提升了很多求教一个多维空间投影的问题大家来看看这个纯Javascript实现的QR二维码生成器凑个热闹也说CS (转载)如何把文字转换成机器可读形式？clarify