中文
devexamples

Quickselect for the Kth Largest Element

Find the kth largest element in average linear time with quickselect, avoiding the cost of fully sorting when only one rank is needed.

JavascriptData Integrity

Code

snippet
export function kthLargest(items, k) {
  if (k < 1 || k > items.length) throw new RangeError("k out of range");
  const target = items.length - k;
  const data = items.slice();
  let left = 0;
  let right = data.length - 1;
  while (true) {
    const pivotIndex = partition(data, left, right);
    if (pivotIndex === target) return data[pivotIndex];
    if (pivotIndex < target) left = pivotIndex + 1;
    else right = pivotIndex - 1;
  }
}

function partition(data, left, right) {
  const pivot = data[right];
  let store = left;
  for (let i = left; i < right; i++) {
    if (data[i] < pivot) {
      [data[i], data[store]] = [data[store], data[i]];
      store++;
    }
  }
  [data[right], data[store]] = [data[store], data[right]];
  return store;
}

Related Examples