b******g
发帖数: 77 | 1 一个martrix，每行每列都是sorted，找到前kth 个
Analysis:
Applying a quick-select algorithm will achieve an O( n * n ) time
complexity. Can we do better? Yes. Here is a algorithm:
1. Like quick-select algorithm, this algorithm applies divide-and-
conquer.
2. Initialize those two boundary lines to (n * [0] and n * [n]) to
include all array items in boundary.
3. Process subarray between boundary lines (lo, hi ) in each
recursive call:
a. select a random item in su... 阅读全帖 |
|
