演算法

1function kthSort(nums: number[], k: number): number {
2  const sorted = [...nums].sort((a, b) => b - a);
3  return sorted[k - 1];
4}
5 
6// A min-heap of the k largest so far: its top is the k-th largest.
7function kthHeap(nums: number[], k: number): number {
8  const h: number[] = [];
9  const swap = (i: number, j: number) => { [h[i], h[j]] = [h[j], h[i]]; };
10  for (const x of nums) {
11    if (h.length < k) {
12      h.push(x);
13      for (let i = h.length - 1; i > 0 && h[i] < h[(i - 1) >> 1]; i = (i - 1) >> 1) swap(i, (i - 1) >> 1);
14    } else if (x > h[0]) {
15      h[0] = x;
16      for (let i = 0; ; ) {
17        const l = 2 * i + 1, r = l + 1;
18        let m = i;
19        if (l < h.length && h[l] < h[m]) m = l;
20        if (r < h.length && h[r] < h[m]) m = r;
21        if (m === i) break;
22        swap(i, m);
23        i = m;
24      }
25    }
26  }
27  return h[0];
28}
29 
30function kthQuickselect(nums: number[], k: number): number {
31  const a = [...nums];
32  const target = a.length - k;
33  let seed = 42, lo = 0, hi = a.length - 1;
34  while (lo < hi) {
35    seed = (Math.imul(seed, 1103515245) + 12345) & 0x7fffffff;
36    const p = lo + (seed % (hi - lo + 1));
37    [a[p], a[hi]] = [a[hi], a[p]];
38    let i = lo;
39    for (let j = lo; j < hi; j++) {
40      if (a[j] < a[hi]) { [a[i], a[j]] = [a[j], a[i]]; i++; }
41    }
42    [a[i], a[hi]] = [a[hi], a[i]];
43    if (i === target) return a[i];
44    if (target < i) hi = i - 1;
45    else lo = i + 1;
46  }
47  return a[lo];
48}
49 
50// Values in 0..max: count each one, then walk down from the largest.
51function kthBucket(nums: number[], k: number): number {
52  const count = new Array(Math.max(...nums) + 1).fill(0);
53  for (const x of nums) count[x]++;
54  let seen = 0;
55  for (let v = count.length - 1; v >= 0; v--) {
56    seen += count[v];
57    if (seen >= k) return v;
58  }
59  throw new Error("k too large");
60}