function rand(min: number, max: number): number {
return Math.trunc(Math.random() * (max - min + 1) + min);
}
function swap(arr: number[], x: number, y: number) {
let temp: number = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
function quickSelect(arr: number[], left: number, right: number, k: number): number {
if (left >= right) return arr[left];
swap(arr, left, rand(left, right));
let privot: number = arr[left];
let mark: number = left;
for (let i: number = left + 1; i <= right; i++) {
if (arr[i] < privot) {
mark++;
swap(arr, mark, i);
}
}
swap(arr, mark, left);
if (mark + 1 == k) {
return arr[mark];
} else if (mark + 1 > k) {
return quickSelect(arr, left, mark - 1, k);
} else {
return quickSelect(arr, mark + 1, right, k);
}
}
function findKthLargest(arr: number[], left: number, right: number, k: number): number {
return quickSelect(arr, left, right, k);
}
const arr: number[] = [4, 5, 1, 3, 2, 8, 6, 7];
const left: number = 0;
const right: number = arr.length - 1;
const k1 = 1;
const k2 = 5;
const k3 = 8;
const result1 = findKthLargest(arr, left, right, arr.length - k1 + 1);
const result2 = findKthLargest(arr, left, right, arr.length - k2 + 1);
const result3 = findKthLargest(arr, left, right, arr.length - k3 + 1);
console.log(result1);
console.log(result2);
console.log(result3);