i*****y
发帖数: 1554 | 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? |
t*****l
发帖数: 121 | 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?
|
s****u
发帖数: 118 | 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?
|
j****g
发帖数: 597 | 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). |
N********n
发帖数: 8363 | 5 A max-heap solution is faster than that.
【在 s****u 的大作中提到】
: k smallest numbers是nth_element的副产品
:
: k
|
p****n
发帖数: 148 | 6 why?
【在 N********n 的大作中提到】
: A max-heap solution is faster than that.
|
e*****w
发帖数: 144 | 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?
|
e*******e
发帖数: 32 | 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
|
