数组中的第K个最大元素

API

const getKMin = (nums, k) => {
return nums.sort((a, b) => b - a)[k-1]
}

时间复杂度：O(nlogn) 空间复杂度：O(logn)

最小堆


const getKMin = (nums, k) => {
if (nums.length < k) return
let heap = [,], i = 0;
while (i < k) {
    heap.push(nums[i++])
}

buildHeap(heap, k)
// 从 k 位开始遍历数组
for (let i = k; i < nums.length; i++) {
    if (nums[i] > heap[1]) {
        // 替换并堆化
        heap[1] = nums[i];
        heapify(heap, k, 1)
    }
}

// 删除heap中第一个元素
heap.shift()
return heap[0]
}

const buildHeap = (heap, k) => { if (k === 1) return // 从最后一个非叶子节点开始 for (let i = Math.floor(k / 2); i > 0; i--) { // 自上而下式堆化 heapify(heap, k, i) } }

// 最小堆化 const heapify = function (arr, k, i) { // 自上而下堆化 while(true) { let minIndex = i if (2i <= k && arr[2i] < arr[minIndex]) { minIndex = 2i } if (2i+1 <= k && arr[2i+1] < arr[minIndex]) { minIndex = 2i + 1 } if (minIndex !== i) { swap(arr, minIndex, i) i = minIndex } else { break } } }

const swap = (arr, i, j) => { let temp = arr[i] arr[i] = arr[j] arr[j] = temp }

时间复杂度：遍历数组需要 **O(n)** 的时间复杂度，一次堆化需要 **O(logk)** 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 **O(nlogk)**
空间复杂度：**O(k)**

* 快速排序
```js
const getKMin = (nums, k) => {
    const len = nums.length;
    if (len < k) return
    quickSelect(nums, 0, len - 1)
    return nums[k-1]
}

const quickSelect = (nums, left, right) => {
    let index
    // left,right可以看成左右两个哨兵
    if (left < right) {
        // 划分数组
        index = partition(nums, left, right)
        if (left < index - 1) {
            quickSelect(nums, left, index - 1)
        }
        if (index < right) {
            quickSelect(nums, index, right)
        }
    }
}

const partition = (nums, left, right) => {
    // 取中间项为基准
    const midNum = nums[Math.floor(Math.random() * (right - left + 1)) + left]
    let i = left, j = right
    // 左右哨兵相遇，第一轮交换结束
    while (i <= j) {
        // 左哨兵右移，直到遇到第一个大于基准的数停下来
        while(nums[i] > midNum) {
            i++
        }
        // 右哨兵左移，直到遇到第一个小于基准的数停下来
        while(nums[j] < midNum) {
            j--
        }
        // 交换左右哨兵所在位置的值
        if (i <= j) {
            swap(nums, i, j)
            i++
            j--
        }
    }
    return i
}

const swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

时间复杂度：O(nlog2n) 空间复杂度：O(nlog2n)

快速选择

上面我们实现了快速排序来取第 k 个最大值，其实没必要那么麻烦，我们仅仅需要在每执行一次快排的时候，比较基准值位置是否在 n-k 位置上，如果小于 n-k ，则第 k 个最大值在基准值的右边，我们只需递归快排基准值右边的子序列即可；如果大于 n-k ，则第 k 个最大值在基准值的做边，我们只需递归快排基准值左边的子序列即可；如果等于 n-k ，则第 k 个最大值就是基准值

let getKMin = function(nums, k) {
    const len = nums.length
    if (len < k) return
    return quickSelect(nums, 0, len - 1, len - k)
};

let quickSelect = (arr, left, right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return arr[index]
    } else if(k < index) {
        // Top k 在左边
        return quickSelect(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return quickSelect(arr, index+1, right, k)
    }
  }
  return arr[left]
}

let partition = (arr, left, right) => {
  // 取中间项为基准
  var midNum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i < j) {

    // 左指针右移
    while(arr[i] < midNum) {
      i++
    }

    // 右指针左移
    while(arr[j] > midNum) {
      j--
    }

    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时，即都为midNum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}

// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

时间复杂度：平均时间复杂度O(n)，最坏情况时间复杂度为O(n2) 空间复杂度：O(1)

中位数的中位数（BFPRT）算法

在BFPTR算法中，仅仅是改变了快速选择（quickselect）算法中 Partion 中的基准值的选取，在快速选择（quickselect）算法中，我们可以选择第一个元素或者最后一个元素作为基准元，优化的可以选择随机一个元素作为基准元，而在 BFPTR 算法中，每次选择五分中位数的中位数作为基准元（也称为主元pivot），这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。时间复杂度最坏为O(n)!!!

代码略，没整明白。

xszi / javascript-algorithms

数组中的第K个最大元素 #77