当前位置: 编程技术>c/c++/嵌入式
数组中求第K大数的实现方法
来源: 互联网 发布时间:2014-10-15
本文导语: 问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料...
问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。
该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表。
该问题还可以变形为:有一个大小为 n的数组A[0,1,2,…,n-1],求其中前k大的数。
一字之差,原问题是“第k大”,变形的问题是“前k大”,但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇。
我们先分析原问题:有一个大小为 n的数组A[0,1,2,…,n-1],求其中第k大的数。
我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可以确定该值,如果k=2,则扫描两边数组就可以确定第二大的数,依此类推下去,时间复杂度是O(k*n),如果k跟n是一个数量级,那么时间复杂度就是O(n*n)了,显然不是最优的解法。
考虑分治法,难点在于如何将该问题分解为两个子问题。
快速排序最基础的一步:
随机取某一个数x,将其与数组末尾元素交换,然后将比其小的数交换至前,比其大的数交换至后。
这一步使某一数组的快速排序问题分解成两个子数组的排序问题,现在我们就依此来解决取第k大的数这个问题。
设数组下表从0开始,至n-1结束。
1、 随机取某个数,将其与数组末尾元素交换。
a) idx=rand(0,n-1);生成[0,n-1]间的随机数。
b) Swap(array[idx], array[n-1]);
2、 用末尾元素x,将比x小的数交换至前,比x大的数交换至后,并返回此时x在数组中的位置mid。
3、 如果mid==n-k,那么返回该值,这就是第k大的数。
如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数。
如果mid
该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们的意料,此处暂且不表。
该问题还可以变形为:有一个大小为 n的数组A[0,1,2,…,n-1],求其中前k大的数。
一字之差,原问题是“第k大”,变形的问题是“前k大”,但是平均时间复杂度却都可以控制在O(n),这不由得让人暗暗称奇。
我们先分析原问题:有一个大小为 n的数组A[0,1,2,…,n-1],求其中第k大的数。
我们先取特例,令k=1,那么就是取最大的数,只要扫描一遍数组就可以确定该值,如果k=2,则扫描两边数组就可以确定第二大的数,依此类推下去,时间复杂度是O(k*n),如果k跟n是一个数量级,那么时间复杂度就是O(n*n)了,显然不是最优的解法。
考虑分治法,难点在于如何将该问题分解为两个子问题。
快速排序最基础的一步:
随机取某一个数x,将其与数组末尾元素交换,然后将比其小的数交换至前,比其大的数交换至后。
这一步使某一数组的快速排序问题分解成两个子数组的排序问题,现在我们就依此来解决取第k大的数这个问题。
设数组下表从0开始,至n-1结束。
1、 随机取某个数,将其与数组末尾元素交换。
a) idx=rand(0,n-1);生成[0,n-1]间的随机数。
b) Swap(array[idx], array[n-1]);
2、 用末尾元素x,将比x小的数交换至前,比x大的数交换至后,并返回此时x在数组中的位置mid。
3、 如果mid==n-k,那么返回该值,这就是第k大的数。
如果mid>n-k,那么第k大的数在左半数组,且在左半数组中是第k-(n-mid)大的数。
如果mid