forked from yangshun/lago
-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSelect.ts
47 lines (39 loc) · 1.14 KB
/
quickSelect.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import randomInt from '../utils/randomInt';
/**
* Returns the kth smallest element in an unsorted array.
* @param {number[]} arr The input array.
* @param {number} k
* @return {number} The kth smallest element in the array.
*/
function quickSelect(arr: Array<number>, k: number): number | null {
if (k < 1 || k > arr.length) {
return null;
}
const pivot = arr[randomInt(0, arr.length - 1)];
const lower: Array<number> = [];
const higher: Array<number> = [];
arr.forEach(num => {
if (num < pivot) {
lower.push(num);
} else if (num > pivot) {
higher.push(num);
}
});
if (k <= lower.length) {
return quickSelect(lower, k);
}
if (k > arr.length - higher.length) {
return quickSelect(higher, k - (arr.length - higher.length));
}
return pivot;
}
/**
* Returns the kth largest element in an unsorted array.
* @param {number[]} arr The input array.
* @param {number} k
* @param {number} The kth largest element in the array.
*/
function quickSelectLargest(arr: Array<number>, k: number): number | null {
return quickSelect(arr, arr.length - k + 1);
}
export { quickSelect, quickSelectLargest };