在无序数组中找到第k大的数

时间：2022-12-30 14:53:01

在N个元素中查找第K大元素，一般比较简单的方法就是先快速排序，然后直接返回array[N - K]或者利用扫描法，每一次扫描都找到当前数组中最大的元素，这个其实就是部分冒泡排序。前一种算法的时间复杂度是O(NlogN)，后一种算法的时间复杂度是K*N。当然，这里我们不打算具体讨论以上两种方案，接下来看看其他方法。

       第一种方法：利用堆排序的思想来查询数组中第K大元素。首先提取子数组array[0...K-1]并构造小顶堆，然后把剩下子数组array[K...N-1]中的所有元素与堆顶元素array[0]进行比较，若大于堆顶元素，则进行交换并重新构造子数组array[0...K-1]使其满足小顶堆的要求。这样的话，最后子数组array[0...K-1]就是N个元素中的前K个最大元素，堆顶array[0]就是N个元素中的第K大元素。具体实现代码如下：

[cpp]  view plain  copy
  1. #include <cstdlib>  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. /***************************************************************************** 
  6.  函 数 名  : small_heap_adjust 
  7.  功能描述  : 根据数组构建小顶堆  
  8.  输入参数  : array  待调整的堆数组 
  9.              index  待调整的数组元素的位置 
  10.              length 数组的长度 
  11.  输出参数  : 无 
  12.  返 回 值  : 无  
  13.  修改历史      : 
  14.   1.日    期   : 2012/09/10 
  15.     作    者   : liguangting 
  16.     修改内容   :  
  17. *****************************************************************************/  
  18. void small_heap_adjust(int *array, int index, int length)  
  19. {  
  20.     int child;  
  21.     int temp = array[index];  
  22.       
  23.     if (2 * index + 1 >= length)  
  24.     {  
  25.         return;  
  26.     }  
  27.   
  28.     //子结点位置 = 2 * 父结点位置 + 1  
  29.     child = 2 * index + 1;  
  30.           
  31.     //得到子结点中较小的结点   
  32.     if (child < length - 1 && array[child + 1] < array[child])  
  33.     {  
  34.         ++child;  
  35.     }  
  36.               
  37.     //如果较小的子结点小于父结点那么把较小的子结点往上移动，替换它的父结点   
  38.     if (temp > array[child])  
  39.     {  
  40.         array[index] = array[child];  
  41.     }  
  42.     else  
  43.     {  
  44.         return;  
  45.     }  
  46.           
  47.     //最后把需要调整的元素值放到合适的位置   
  48.     array[child] = temp;  
  49.       
  50.     small_heap_adjust(array, child, length);  
  51. }  
  52.   
  53. /***************************************************************************** 
  54.  函 数 名  : find_kmax_value 
  55.  功能描述  : 查找数组中第K大元素  
  56.  输入参数  : array  待查询的数组  
  57.              length 数组的长度 
  58.              K      第K大  
  59.  输出参数  : 无 
  60.  返 回 值  : 返回第K大元素  
  61.  修改历史      : 
  62.   1.日    期   : 2012/09/10 
  63.     作    者   : liguangting 
  64.     修改内容   :  
  65. *****************************************************************************/  
  66. int find_kmax_value(int *array, int length, int k)  
  67. {  
  68.     int i = 0;  
  69.       
  70.     //把子数组array[0...k-1]构造成小顶堆   
  71.     for (i = k / 2 - 1; i >= 0; i--)  
  72.     {  
  73.         small_heap_adjust(array, i, k);  
  74.     }  
  75.       
  76.     //子数组array[k...length-1]的所有元素与堆顶元素进行比较，若大于堆顶元素  
  77.     //则交换，并重新调整堆   
  78.     for (i = k; i < length; i++)  
  79.     {  
  80.         if (array[i] > array[0])  
  81.         {  
  82.             swap(array[0], array[i]);  
  83.             small_heap_adjust(array, 0, k);  
  84.         }  
  85.     }  
  86.       
  87.     return array[0];  
  88. }  
  89.   
  90. int main(int argc, char *argv[])  
  91. {  
  92.     const int LENGTH = 100;  
  93.     const int K = 30;  
  94.     int array[LENGTH] = {0};  
  95.     int kmax = 0;  
  96.     srand(time(NULL));  
  97.     cout << "原始数组:" << endl;   
  98.     for (int i = 0; i < LENGTH; i++)  
  99.     {  
  100.         array[i] = rand() % 100;  
  101.         cout << array[i] << " ";  
  102.         if (0 == (i + 1) % 10)  
  103.         {  
  104.             cout << endl;  
  105.         }  
  106.     }  
  107.       
  108.     kmax = find_kmax_value(array, LENGTH, K);  
  109.     cout << "第K大元素:" << kmax << endl;  
  110.   
  111.     sort(array, array + LENGTH);  
  112.     cout << "排序后数组:" << endl;  
  113.     for (int i = 0; i < LENGTH; i++)  
  114.     {  
  115.         cout << array[i] << " ";  
  116.         if (0 == (i + 1) % 10)  
  117.         {  
  118.             cout << endl;  
  119.         }  
  120.     }  
  121.       
  122.     if (kmax == array[LENGTH - K])  
  123.     {  
  124.         cout << "查找第K大元素成功！" << endl;  
  125.     }  
  126.     system("PAUSE");  
  127.     return EXIT_SUCCESS;  
  128. }  


       第二种方法：同样是利用堆排序的思想，但采用的是大顶堆，并且结合部分排序的思想。大致思路：首先把数组array[0...N-1]构造成大顶堆，然后依次提取当前堆中最大的元素，直到找到第K大元素。具体实现代码如下：

[cpp]  view plain  copy
  1. /***************************************************************************** 
  2.  函 数 名  : big_heap_adjust 
  3.  功能描述  : 根据数组构建大顶堆  
  4.  输入参数  : array  待调整的堆数组 
  5.              index  待调整的数组元素的位置 
  6.              length 数组的长度  
  7.  输出参数  : 无 
  8.  返 回 值  : 无  
  9.  修改历史      : 
  10.   1.日    期   : 2012/09/10 
  11.     作    者   : liguangting 
  12.     修改内容   :  
  13. *****************************************************************************/  
  14. void big_heap_adjust(int *array, int index, int length)  
  15. {  
  16.     int child;  
  17.     int temp = array[index];  
  18.       
  19.     if (2 * index + 1 >= length)  
  20.     {  
  21.         return;  
  22.     }  
  23.   
  24.     //子结点位置 = 2 * 父结点位置 + 1  
  25.     child = 2 * index + 1;  
  26.           
  27.     //得到子结点中较大的结点   
  28.     if (child < length - 1 && array[child + 1] > array[child])  
  29.     {  
  30.         ++child;  
  31.     }  
  32.               
  33.     //如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点   
  34.     if (temp < array[child])  
  35.     {  
  36.         array[index] = array[child];  
  37.     }  
  38.     else  
  39.     {  
  40.         return;  
  41.     }  
  42.           
  43.     //最后把需要调整的元素值放到合适的位置   
  44.     array[child] = temp;  
  45.       
  46.     big_heap_adjust(array, child, length);  
  47. }  
  48.   
  49. /***************************************************************************** 
  50.  函 数 名  : find_kmax_value 
  51.  功能描述  : 查找数组中第K大元素  
  52.  输入参数  : array  待查询的数组  
  53.              length 数组的长度 
  54.              K      第K大  
  55.  输出参数  : 无 
  56.  返 回 值  : 返回第K大元素  
  57.  修改历史      : 
  58.   1.日    期   : 2012/09/10 
  59.     作    者   : liguangting 
  60.     修改内容   :  
  61. *****************************************************************************/  
  62. int find_kmax_value(int *array, int length, int k)  
  63. {  
  64.     int i = 0;  
  65.       
  66.     //把子数组array[0...length-1]构造成大顶堆   
  67.     for (i = length / 2 - 1; i >= 0; i--)  
  68.     {  
  69.         big_heap_adjust(array, i, length);  
  70.     }  
  71.       
  72.     //从最后一个元素开始对数组进行调整，不断缩小调整的范围直到第length - k个元素   
  73.     for (i = length - 1; i >= length - k; i--)  
  74.     {  
  75.         //交换第一个元素和当前的最后一个元素，保证当前的最后一个元素在当前数组中是最大的   
  76.         swap(array[0], array[i]);  
  77.           
  78.         //调整完后的第一个元素是当前数组的最大元素   
  79.         big_heap_adjust(array, 0, i);  
  80.     }  
  81.       
  82.     return array[length - k];  
  83. }  



       总结：以上两种方法同样都是用堆排序的思想来查找第K大元素，那到底有何区别呢？我们主要来看一下时空间复杂度：

       1、小顶堆：时间复杂度为O(NlogK)，额外空间为O(K)。

       2、大顶堆：时间复杂度为O(KlogN)，额外空间为O(N)。

       在数据量不是很大的情况下，可能以上两种方法的差别并不是特别大。但是，当数据量大到一定程度后，两者的差别就非常明显了。例如：一个文件中有100000000个整数，要求找出第10000大元素。用第一种方法的时间复杂度为100000000log10000，额外空间为10000；用第二种方法的时间复杂度为10000log100000000，额外空间为100000000。在这种情况下，需要用哪一种方法就取决于当时的运行环境、时空要求等因素，或者我们再去寻求时空间复杂度更低的方案。

标签：

相关文章