数组中的第K个最大元素

[xszi]

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

说明:

• 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

leetcode

[xszi]

• 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 (2*i <= k && arr[2*i] < arr[minIndex]) {
            minIndex = 2*i
        }
        if (2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
            minIndex = 2*i + 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)

• 快速排序

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)!!!

代码略，没整明白。