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
相关阅读
能否创立一个functional programming的版面java GZip 求助gcc的网页断了？？C++ 什么时候用 "new" ?python decorator 调用问题请问个老的COMBINATION题如果我有一些.mp3文件，怎样用Java把这些音频文件按照不同时间间隔来合成一个mp3文件？请问有人知道如何在matlab中调用R 吗？partial_sort问题lex/yacc如何reset buffer？default linkage for const global variable in C/C++C#程序调用Windows C++ DLL的问题C++ questionc中什么矩阵库可以做初始化转置相乘相加等基本运算？请问个BufferedReader 读 file 的问题 (转载)在帮忙看看这个吧 C： int->char*Is the order of initialization a, b, c or c, b, a?operator commaC/C++ 中 & | << 这些运算对哪些数据类型定义了阿？怎样清理不要的C代码