体会编程之美,找出最大的k个数

 今日上课无事,偶尔看到《编程之美》的一道题目,如何找出n个数中的最大的k个数,不仅惊奇于其提供的多种解法,而且感叹其中很多解法都是之前的我们熟悉解法的变种。废话不多说,我们来依次看一下不同的解法和相应的分析

思路一

  1. 使用排序算法先对n个数进行排序,然后取最大的k个数。
  2. 先找出n个数中最大值,然后在找出n-1个数中的最大值,一直进行,知道找出k个数。

 我们来分析一下两种方法的效率,如果使用快排进行排序,那么时间复杂度就是O(nlog2n),而第二个方法的时间复杂度为O(kn),所以二者的效率高低取决于k相对于log2n的大小,如果k>log2n,那么使用第一种方法比较好,反之,便是使用第二种方法比较好。

思路二

 使用顺序统计量的思路:在一个有n个元素组成的集合中,第i个顺序统计数就是该集合中第i小的元素。对《算法导论》中利用快排查找n个数中中位数的算法进行修改。
在本问题中,假设N个数存储在数组S中,我们从数组S中随机找出一个元素X,从而把数组分为Sa和Sb,Sa中的元素都大于等于X,Sb中的元素都是小于X
  这个时候有
  1 .Sa中的元素个数小于k,Sa中的所有的数和Sb中的最大的k-|Sa|个元素为数组S中最大的k个数
  2 .Sa中的元素大于或者等于k,则需返回Sa中的最大的k个元素。
 这也是二分法思想的体现。

思路三

 使用动态编程的思想,并且解决上述解法中都要多次读取n个数的问题,当n大到一定程度之后,这样会很耗费时间。
主要思想就是维持一个规模为k的数据结构,存储最大的k个值,然后依次遍历n个数,如果发现比数据结构中数小的值,就对数据结构进行更新,遍历结束之后,数据结构中就是n个数中的最大的n个数
 如果使用数组来表示数据结构,那么时间复杂度就是O(kn),但如果使用最小堆来表示,那么时间复杂读就是O(nlog2k)。

思路四

 上述的思路都是基于n个数相互比较的解法,如同《算法导论》中的想法,我们可以使用其他方式的比较来获得n个数的大小关系。所以,如果n个数都是在一个整数范围之内,我们可以修改计数排序和基数排序来找出最大的k个数。

1000 Compartir