阅读 2310

前端进阶算法:别再说你不懂topk问题了

引言

今天这篇文章讲解一道活跃于各个大厂(腾讯、字节、阿里等)面试中的题目:Top K 问题,将按照以下脉络介绍:

  • 什么是 Top K 问题
  • Top K 问题的五种经典解法
  • 快速回顾与总结
  • 练习题 Top K 三剑客:最小 K 个数、前 K 个高频元素、第 K 个最小元素(含解答)

下面直接开始吧👇

一、什么是 Top K 问题

什么是 Top K 问题?简单来说就是在一组数据里面找到频率出现最高的前 K 个数,或前 K 大(当然也可以是前 K 小)的数。

经典的 Top K 问题有:最大(小) K 个数、前 K 个高频元素、第 K 个最大(小)元素

下面以求数组中的第 K 个最大元素为例,介绍 Top K 问题的解法

题目:

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

示例:

输入: [4,5,1,6,2,7,3,8] 和 k = 4
输出: 5
复制代码

二、解法:全局排序,取第 k 个数

我们能想到的最简单的就是将数组进行排序(可以是最简单的快排),取前 K 个数就可以了,so easy

代码实现:

let findKthLargest = function(nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k-1]
};
复制代码

复杂度分析:

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(logn)

注意:

在 V8 引擎 7.0 版本之前,数组长度小于10时, Array.prototype.sort() 使用的是插入排序,否则用快速排序。

在 V8 引擎 7.0 版本之后就舍弃了快速排序,因为它不是稳定的排序算法,在最坏情况下,时间复杂度会降级到 O(n2)。

而是采用了一种混合排序的算法:TimSort

这种功能算法最初用于Python语言中,严格地说它不属于以上10种排序算法中的任何一种,属于一种混合排序算法:

在数据量小的子数组中使用插入排序,然后再使用归并排序将有序的子数组进行合并排序,时间复杂度为 O(nlogn)

三、解法:局部排序,冒泡

题目仅仅需要求出数组中的第K个最大元素,没必要对数组整体进行排序

可以使用冒泡排序,每次将最大的数在最右边冒泡出来,只冒泡 k次即可

动图演示

代码实现

let findKthLargest = function(nums, k) {
    // 进行k轮冒泡排序
    bubbleSort(nums, k)
    return nums[nums.length-k]
}

let bubbleSort = function(arr, k) {
    for (let i = 0; i < k; i++) {
        // 提前退出冒泡循环的标识位
        let flag = false;
        for (let j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
                // 表示发生了数据交换
            }
        }
        // 没有数据交换
        if(!flag) break
    }
}
复制代码

复杂度分析:

  • 时间复杂度:最好时间复杂度 O(n),平均时间复杂度 O(n*k)
  • 空间复杂度:O(1)

四、解法:构造前 k 个最大元素小顶堆,取堆顶

我们也可以通过构造一个前 k 个最大元素小顶堆来解决,小顶堆上的任意节点值都必须小于等于其左右子节点值,即堆顶是最小值。

所以我们可以从数组中取出 k 个元素构造一个小顶堆,然后将其余元素与小顶堆对比,如果大于堆顶则替换堆顶,然后堆化,所有元素遍历完成后,堆中的堆顶即为第 k 个最大值

具体步骤如下:

  • 从数组中取前 k 个数( 0k-1 位),构造一个小顶堆
  • k 位开始遍历数组,每一个数据都和小顶堆的堆顶元素进行比较,如果小于堆顶元素,则不做任何处理,继续遍历下一元素;如果大于堆顶元素,则将这个元素替换掉堆顶元素,然后再堆化成一个小顶堆。
  • 遍历完成后,堆顶的数据就是第 K 大的数据

代码实现:

let findKthLargest = function(nums, k) {
    // 从 nums 中取出前 k 个数,构建一个小顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(nums[i++]) 
    }
    buildHeap(heap, k)
    
    // 从 k 位开始遍历数组
    for(let i = k; i < nums.length; i++) {
        if(heap[1] < nums[i]) {
            // 替换并堆化
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    
    // 返回堆顶元素
    return heap[1]
};

// 原地建堆,从后往前,自上而下式建小顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始,自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}

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

// 交换
let 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)

利用堆求 Top k 问题的优势

这种求 Top k 问题是可以使用排序来处理,但当我们需要在一个动态数组中求 Top k 元素怎么办喃?

动态数组可能会插入或删除元素,难道我们每次求 Top k 问题的时候都需要对数组进行重新排序吗?那每次的时间复杂度都为 O(nlogn)

这里就可以使用堆,我们可以维护一个 K 大小的小顶堆,当有数据被添加到数组中时,就将它与堆顶元素比较,如果比堆顶元素大,则将这个元素替换掉堆顶元素,然后再堆化成一个小顶堆;如果比堆顶元素小,则不做处理。这样,每次求 Top k 问题的时间复杂度仅为 O(logk)

更多堆内容可查看 前端进阶算法9:看完这篇,再也不怕堆排序、Top K、中位数问题面试了

五、解法:优化,快速选择(quickselect)算法

无论是排序算法还是构造堆求解 Top k问题,我们都经过的一定量的不必要操作:

  • 如果使用排序算法,我们仅仅想要的是第 k 个最大值,但是我们却对数组进行了整体或局部的排序
  • 如果使用堆排序,需要维护一个大小为 k 的堆(大顶堆,小顶堆),同时花费时间也很昂贵,时间复杂度为 O(nlogk)

那么有没有一种算法,不需要进行排序,也不需要花费额外的空间,就能获取第 K 个最大元素喃?

这就要说到快速选择算法了😊

快速选择(quickselect)算法与快排思路上相似,下面普及一下快排,已经了解的朋友可以跳过这一段

快排

快排使用了分治策略的思想,所谓分治,顾名思义,就是分而治之,将一个复杂的问题,分成两个或多个相似的子问题,在把子问题分成更小的子问题,直到更小的子问题可以简单求解,求解子问题,则原问题的解则为子问题解的合并。

快排的过程简单的说只有三步:

  • 首先从序列中选取一个数作为基准数
  • 将比这个数大的数全部放到它的右边,把小于或者等于它的数全部放到它的左边 (一次快排 partition
  • 然后分别对基准的左右两边重复以上的操作,直到数组完全排序

具体按以下步骤实现:

  • 1,创建两个指针分别指向数组的最左端以及最右端
  • 2,在数组中任意取出一个元素作为基准
  • 3,左指针开始向右移动,遇到比基准大的停止
  • 4,右指针开始向左移动,遇到比基准小的元素停止,交换左右指针所指向的元素
  • 5,重复3,4,直到左指针超过右指针,此时,比基准小的值就都会放在基准的左边,比基准大的值会出现在基准的右边
  • 6,然后分别对基准的左右两边重复以上的操作,直到数组完全排序

注意这里的基准该如何选择喃?最简单的一种做法是每次都是选择最左边的元素作为基准:

但这对几乎已经有序的序列来说,并不是最好的选择,它将会导致算法的最坏表现。还有一种做法,就是选择中间的数或通过 Math.random() 来随机选取一个数作为基准,下面的代码实现就是以随机数作为基准。

代码实现

let quickSort = (arr) => {
  quick(arr, 0 , arr.length - 1)
}

let quick = (arr, left, right) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    if(left < index - 1) {
      quick(arr, left, index - 1)
    }
    if(index < right) {
      quick(arr, index, right)
    }
  }
}

// 一次快排
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i <= j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i <= j) {
      swap(arr, i, j)
      i += 1
      j -= 1
    }
  }
  return i
}

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

// 测试
let arr = [1, 3, 2, 5, 4]
quickSort(arr)
console.log(arr) // [1, 2, 3, 4, 5]
// 第 2 个最大值
console.log(arr[arr.length - 2])  // 4
复制代码

快排是从小到大排序,所以第 k 个最大值在 n-k 位置上

复杂度分析

  • 时间复杂度:O(nlogn)
  • 空间复杂度:O(nlogn)

快速选择(quickselect)算法

上面我们实现了快速排序来取第 k 个最大值,其实没必要那么麻烦,

我们仅仅需要在每执行一次快排的时候,比较基准值位置是否在 n-k 位置上,

  • 如果小于 n-k ,则第 k 个最大值在基准值的右边,我们只需递归快排基准值右边的子序列即可;
  • 如果大于 n-k ,则第 k 个最大值在基准值的做边,我们只需递归快排基准值左边的子序列即可;
  • 如果等于 n-k ,则第 k 个最大值就是基准值

代码实现:

let findKthLargest = function(nums, k) {
    return quickSelect(nums, nums.length - k)
};

let quickSelect = (arr, k) => {
  return quick(arr, 0 , arr.length - 1, k)
}

let quick = (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 quick(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return quick(arr, index+1, right, k)
    }
  }
  return arr[left]
}

let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i < j) swap(arr, i, j)

    // 当数组中存在重复数据时,即都为datum,但位置不同
    // 继续递增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)算法

又称为中位数的中位数算法,它的最坏时间复杂度为 O(n) ,它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。

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

BFPRT 算法步骤如下:

  • 选取主元
    • 将 n 个元素按顺序分为 n/5 个组,每组 5 个元素,若有剩余,舍去
    • 对于这 n/5 个组中的每一组使用插入排序找到它们各自的中位数
    • 对于上一步中找到的所有中位数,调用 BFPRT 算法求出它们的中位数,作为主元;
  • 以主元为分界点,把小于主元的放在左边,大于主元的放在右边;
  • 判断主元的位置与 k 的大小,有选择的对左边或右边递归

代码实现:

let findKthLargest = function(nums, k) {
    return nums[bfprt(nums, 0, nums.length - 1, nums.length - k)]
}

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

let partition = (arr, left, right) => {
  // 基准
  var datum = arr[findMid(arr, left, right)],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    
    // 交换
    if(i < j) swap(arr, i, j)

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

/**
 * 数组 arr[left, right] 每五个元素作为一组,并计算每组的中位数,
 * 最后返回这些中位数的中位数下标(即主元下标)。
 *
 * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思,
 * 这样可以始终保持 k 大于 0。
 */
let findMid = (arr, left, right) => {
    if (right - left < 5)
        return insertSort(arr, left, right);

    let n = left - 1;

    // 每五个作为一组,求出中位数,并把这些中位数全部依次移动到数组左边
    for (let i = left; i + 4 <= right; i += 5)
    {
        let index = insertSort(arr, i, i + 4);
        swap(arr[++n], arr[index]);
    }

    // 利用 bfprt 得到这些中位数的中位数下标(即主元下标)
    return findMid(arr, left, n);
}

/**
 * 对数组 arr[left, right] 进行插入排序,并返回 [left, right]
 * 的中位数。
 */
let insertSort = (arr, left, right) => {
    let temp, j
    for (let i = left + 1; i <= right; i++) {
        temp = arr[i];
        j = i - 1;
        while (j >= left && arr[j] > temp)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
    return ((right - left) >> 1) + left;
}

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

复杂度分析:

为什么是5?

在BFPRT算法中,为什么是选5个作为分组?

首先,偶数排除,因为对于奇数来说,中位数更容易计算。

如果选用3,有

,其操作元素个数还是 n

如果选取7,9或者更大,在插入排序时耗时增加,常数 c 会很大,有些得不偿失。

七、回顾与总结

最后,我们总结一下,求topk问题其实并不难,主要有以下几个思路:

  • 整体排序:O(nlogn)
  • 局部排序:只冒泡排序前k个最大值,O(n*k)
  • 利用堆:O(nlogk)
  • 计数或桶排序:计数排序用于前k个最值,时间复杂度为O(n + m),其中 m 表示数据范围;桶排序用于最高频k个,时间复杂度为O(n); 但这两者都要求输入数据必须是有确定范围的整数 ,本文没有做过多介绍,可前往 github.com/sisterAn/Ja… 查看堆系列获取更多信息
  • 优化:快速选择(quickselect)算法:平均O(n),最坏O(n2)
  • 继续优化:中位数的中位数(bfprt)算法:最坏O(n)

这里简单说一下后两种方案:

  • 首先,需要知道什么是快排,快排的过程简单的说只有三步:首先从序列中选取一个数作为基准数;将比这个数大的数全部放到它的右边,把小于或者等于它的数全部放到它的左边 (一次快排 partition);然后分别对基准的左右两边重复以上的操作,直到数组完全排序

  • 快速选择(quickselect)算法:快排会把所有的数据进行排序,而我们仅仅想要的是第 k 个最大值,所以 quickselect 对快排进行来优化:在每执行一次快排(partition)的时候,比较基准值位置是否在 n-k (第k大=第n-k小,n为数组长度)位置上,如果小于 n-k ,则第 k 个最大值在基准值的右边,我们只需递归快排基准值右边的子序列即可;如果大于 n-k ,则第 k 个最大值在基准值的做边,我们只需递归快排基准值左边的子序列即可;如果等于 n-k ,则第 k 个最大值就是基准值,平均时间复杂度O(n),最坏情况时间复杂度为O(n2),在最坏情况下,时间复杂度还是很高的

  • 中位数的中位数(bfprt)算法:该算法的思想是修改快速选择(quickselect)算法的主元选取方法,提高算法在最坏情况下的时间复杂度

最后,附上Top K问题经典练习题,解题内容太多,前往git仓库查看解答

往期精彩

感谢阅读

欢迎关注「前端瓶子君」,回复「交流」加入前端交流群!

欢迎关注「前端瓶子君」,回复「算法」自动加入,从0到1构建完整的数据结构与算法体系!

在这里,瓶子君不仅介绍算法,还将算法与前端各个领域进行结合,包括浏览器、HTTP、V8、React、Vue源码等。

在这里(算法群),你可以每天学习一道大厂算法编程题(阿里、腾讯、百度、字节等等)或 leetcode,瓶子君都会在第二天解答哟!

另外,每周还有手写源码题,瓶子君也会解答哟!