Skip to main content

215. Kth Largest Element in an Array

分析

涉及快排 和 堆排序,堆排序暂不研究

最简单形式的快排

function quickSort(arr: number[]): number[] {
const len = arr.length
if (len <= 1) {
return arr
}
const pivot = arr[0]
const subArr = arr.slice(1)
const left = subArr.filter(value => value < pivot)
const right = subArr.filter(value => value >= pivot)

return [...quickSort(left), pivot, ...quickSort(right)]
}

不借助新数组来进行 partition ,对传入的 arr 自己进行 partition

function quickSort(arr: number[]): number[] {

// 帮助 quickSort 对 arr数组的 [left, right] 区间进行排序
const help = (left: number, right: number) => {
if (left > right) {
return
}
const pivotIndex = partition(left, right)
help(left, pivotIndex - 1)
help(pivotIndex + 1, right)
}

/**
* 对 arr [left, right] 区间进行分区
* 以 arr[left] 作为 pivot 参考点,函数返回 pivotIndex
* 最终使得 arr 满足
* [left, pivotIndex] 均 < pivot
* [pivotIndex+1, right] 均 >= pivot
*/
const partition = (left: number, right: number): number => {
const pivot = arr[left]
let lessThan = left
// [left + 1, lt] 满足 所有值都 < pivot
for (let i = left + 1; i <= right; i++) {
if (arr[i] < pivot) {
lessThan++
if (lessThan === i) {
continue
}
[arr[i], arr[lessThan]] = [arr[lessThan], arr[i]]
}
}
[arr[left], arr[lessThan]] = [arr[lessThan], arr[left]]
return lessThan
}

help(0, arr.length - 1)

return arr
}

题解