我正在努力解决流行的采访问题Find the k-th smallest number in an array of distinct integers
。我读了一些解决方案,发现堆数据结构非常适合这个问题。
因此,我尝试使用Collections框架的PriorityQueue
类实现一个解决方案,假设它在功能上与堆相同。
这是我尝试过的代码:
public static int getKthMinimum(int[] input, int k){
PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
// Total cost of building the heap - O(n) or O(n log n) ?
for(int num : input){
heap.add(num); // Add to heap - O(log n)
}
// Total cost of removing k smallest elements - O(k log n) < O(n) ?
while(k > 0){
heap.poll(); // Remove min - O(log n)
k--;
}
return heap.peek(); // Fetch root - O(1)
}
基于docs,poll和add方法需要O(log n)时间并且peek需要恒定时间。
while
循环的时间复杂度是多少? (我想O(k log n))。1.
while
循环的时间复杂度是多少? (我想O(k log n))。
O(k log n)是正确的。
2.为了这个问题,O(k log n)是否应被视为高于O(n)?是否有切换的阈值?
你不能假设。 k可以是0到n-1之间的任何值,这意味着k log n可以是0到n log n之间的任何值。
3.此代码的总时间复杂度是多少?是O(n)吗?
O(n log n),因为这是构建堆的成本。
可以在O(n)时间内构建堆,但是你的代码不会这样做;如果是这样,你的总复杂度将是O(n + k log n),或等价地,O(MAX(n,k log n))。
4.如果还没有O(n),有没有办法在O(n)中解决它,同时使用PriorityQueue类?
没有。在最坏情况下O(n)时间存在selection algorithms,但它们有点复杂,并且它们不使用PriorityQueue
。
基于PriorityQueue
的最快解决方案需要O(MAX(n,n log MIN(k,n-k)))时间。 (关键是在迭代时只保留堆中的k个最小元素 - 或者n-k个最大元素并使用max-heap,如果k足够大则值得。)