• 此篇博文主要是对面试过程中的算法题进行记录。
  • 该题作为面试常见题型,同时拥有多种实现方式。
  • 后续会对相关算法进行具体代码实现。

题目描述:

有很多个无序的数,怎么选出其中最大的若干个数?即,从n个数中选出最大的K个数。

解法一:

元素数量不多的情况下,使用对应的排序算法来对数据进行排序,再输出最大的前K个数。

两种排序(部分排序,全部排序)

全部排序:( 时间复杂度均为O(Nlog2N) )
快速排序:
  • 选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
堆排序:
  • 创建大顶堆或小顶堆,然后将第一个和最后一个节点进行交换,输出最后一个节点,再调整堆
存在的问题:
  • 即便是K=1的情况,上面的算法复杂度仍然是O(Nlog2N),而显然,我们可以通过n-1此的比较和交换得到结果,不需要对整个数组进行排序。
  • 要避免做后面N-K个数的排序,可以使用部分排序算法,
部分排序:把n个数中的前K个数排序出来,复杂度是O(N*K)。
选择排序:
  • 假设第一个是最小的数,遍历该数之后的数比较大小,若更小,则min指向该数,循环遍历下来之后每一次都能找到未排序数组中的最小值。
冒泡排序:
  • 每次比较相邻的两个数,根据大小关系进行交换。一趟下来,最大值位于最后

结论:

  • 哪一个更好呢?O(nlog2n) 和O(n*K)?这取决于K的大小,在K<log2n的情况下,可以选择部分排序。

解法二

利用快速排序的思想

快排回顾:
  • 快排中的每一步,都是将数据分为两组,其中一组的任何数都小于另一组中的任何数,不断地对数据进行分割直到不能再分即完成排序。
解决方案:
  • 假设n个数存储在数组S中,从S中找出一个元素X,它把数组分为比它大的和比它小的两部分,假设比它大的一部分数组是Smax,比它小的部分是Smin。
  • 此时两种情况:
    • Smax中元素不足K个,说明Smax中的所有数和Smin中最大的K-|Smax|个元素就是数组S中最大的K个数;对于Smin则递归进行对应的操作。
    • Smax中元素的个数大于或等于K,则需要返回Smax中最大的K个元素。
结论:
  • 递归下去,问题的规模不断地变小,平均时间复杂度O(n * log2K)。

解法三(部分堆排序实现)

前两个解法都存在统一的问题,需要对数据访问多次,只能适用于数据量较小的情况。若数据量较大,则不能全部装入内存,所以要求尽可能少地遍历数据。

  • 最好的情况就是K个数,则该K个数则为最大的K个数。如果有K+1个数,则需要比较原K个数中最小的数min和后新加入的一个数temp。若temp>min,则temp替换min。
  • 对于第K+2和K+3个数则与之同理。
步骤概括:所耗费的时间复杂度为O(n * K)。
  • 判断前一步是否有交换?
  • 若有寻找出K个值中最小的值,若无保持上一次的最小值
  • 比较要新加入的值和选出的最小值
  • 若temp>min,则替换对应的min,否则保持
对于寻找最小值以及替换的问题
  • 可以利用堆排序来实现
堆排序实现:
  • 可以使用容量为K的最小堆来存储最大的K个数、最小堆的堆顶就是最小值,考虑加入新的元素时,则只需要比较堆顶和新加入的元素的大小,来对应的进行堆顶的替换。与此同时进行堆结构的调整。保证最小堆的性质。更新过程花费的时间复杂度为O(log2K)。
  • 此时的时间复杂度则为O(n * log2K)
后续会用相关代码实现。敬请期待! 😃