TA貢獻(xiàn)1887條經(jīng)驗(yàn) 獲得超5個贊
我之前在采訪中已經(jīng)做到了，最優(yōu)雅/最有效的方法之一是
O(n log k).
with space: O(k) (thanks, @Nzbuu)
基本上，您將使用大小限制為k的最大堆。對于數(shù)組中的每個項(xiàng)目，請檢查其是否小于最大值（僅O（1））。如果是，則將其放入堆（O（log k））并刪除最大值。如果更大，請轉(zhuǎn)到下一個項(xiàng)目。
當(dāng)然，堆不會產(chǎn)生k個項(xiàng)目的排序列表，但是可以在O（k log k）中完成，這很容易。
同樣，對于找到最大的k個項(xiàng)目，您可以執(zhí)行相同的操作，在這種情況下，您將使用最小堆。
TA貢獻(xiàn)1860條經(jīng)驗(yàn) 獲得超8個贊
對此問題的最佳解決方案如下：使用快速排序找到軸，并丟棄該第k個元素所在的部分，然后遞歸地找到下一個軸。（這是kth Max finder，您需要更改if else條件使其成為kth Min Finder）。這是JavaScript代碼-
// Complexity is O(n log(n))
var source = [9, 2, 7, 11, 1, 3, 14, 22];
var kthMax = function(minInd, MaxInd, kth) {
// pivotInd stores the pivot position
// for current iteration
var temp, pivotInd = minInd;
if (minInd >= MaxInd) {
return source[pivotInd];
}
for (var i = minInd; i < MaxInd; i++) {
//If an element is greater than chosen pivot (i.e. last element)
//Swap it with pivotPointer element. then increase ponter
if (source[i] > source[MaxInd]) {
temp = source[i];
source[i] = source[pivotInd];
source[pivotInd] = temp;
pivotInd++;
}
}
// we have found position for pivot elem.
// swap it to that position place .
temp = source[pivotInd];
source[pivotInd] = source[MaxInd];
source[MaxInd] = temp;
// Only try to sort the part in which kth index lies.
if (kth > pivotInd) {
return kthMax(pivotInd + 1, MaxInd, kth);
} else if (kth < pivotInd) {
return kthMax(minInd, pivotInd - 1, kth);
} else {
return source[pivotInd];
}
}
// last argument is kth-1 , so if give 2 it will give you,
// 3rd max which is 11
console.log(kthMax(0, source.length - 1, 2));
舉報(bào)