• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C语言查找数组中第K大的元素

OC/C/C++ 水墨上仙 2694次浏览

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

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp第一种方法:利用堆排序的思想来查询数组中第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大元素。具体实现代码如下:

#include <cstdlib>  
#include <iostream>  
using namespace std;  
  
/***************************************************************************** 
 函 数 名  : small_heap_adjust 
 功能描述  : 根据数组构建小顶堆  
 输入参数  : array  待调整的堆数组 
             index  待调整的数组元素的位置 
             length 数组的长度 
 输出参数  : 无 
 返 回 值  : 无  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
void small_heap_adjust(int *array, int index, int length)  
{  
    int child;  
    int temp = array[index];  
      
    if (2 * index + 1 >= length)  
    {  
        return;  
    }  
  
    //子结点位置 = 2 * 父结点位置 + 1  
    child = 2 * index + 1;  
          
    //得到子结点中较小的结点   
    if (child < length - 1 && array[child + 1] < array[child])  
    {  
        ++child;  
    }  
              
    //如果较小的子结点小于父结点那么把较小的子结点往上移动,替换它的父结点   
    if (temp > array[child])  
    {  
        array[index] = array[child];  
    }  
    else  
    {  
        return;  
    }  
          
    //最后把需要调整的元素值放到合适的位置   
    array[child] = temp;  
      
    small_heap_adjust(array, child, length);  
}  
  
/***************************************************************************** 
 函 数 名  : find_kmax_value 
 功能描述  : 查找数组中第K大元素  
 输入参数  : array  待查询的数组  
             length 数组的长度 
             K      第K大  
 输出参数  : 无 
 返 回 值  : 返回第K大元素  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
int find_kmax_value(int *array, int length, int k)  
{  
    int i = 0;  
      
    //把子数组array[0...k-1]构造成小顶堆   
    for (i = k / 2 - 1; i >= 0; i--)  
    {  
        small_heap_adjust(array, i, k);  
    }  
      
    //子数组array[k...length-1]的所有元素与堆顶元素进行比较,若大于堆顶元素  
    //则交换,并重新调整堆   
    for (i = k; i < length; i++)  
    {  
        if (array[i] > array[0])  
        {  
            swap(array[0], array[i]);  
            small_heap_adjust(array, 0, k);  
        }  
    }  
      
    return array[0];  
}  
  
int main(int argc, char *argv[])  
{  
    const int LENGTH = 100;  
    const int K = 30;  
    int array[LENGTH] = {0};  
    int kmax = 0;  
    srand(time(NULL));  
    cout << "原始数组:" << endl;   
    for (int i = 0; i < LENGTH; i++)  
    {  
        array[i] = rand() % 100;  
        cout << array[i] << " ";  
        if (0 == (i + 1) % 10)  
        {  
            cout << endl;  
        }  
    }  
      
    kmax = find_kmax_value(array, LENGTH, K);  
    cout << "第K大元素:" << kmax << endl;  
  
    sort(array, array + LENGTH);  
    cout << "排序后数组:" << endl;  
    for (int i = 0; i < LENGTH; i++)  
    {  
        cout << array[i] << " ";  
        if (0 == (i + 1) % 10)  
        {  
            cout << endl;  
        }  
    }  
      
    if (kmax == array[LENGTH - K])  
    {  
        cout << "查找第K大元素成功!" << endl;  
    }  
    system("PAUSE");  
    return EXIT_SUCCESS;  
}  

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

/***************************************************************************** 
 函 数 名  : big_heap_adjust 
 功能描述  : 根据数组构建大顶堆  
 输入参数  : array  待调整的堆数组 
             index  待调整的数组元素的位置 
             length 数组的长度  
 输出参数  : 无 
 返 回 值  : 无  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
void big_heap_adjust(int *array, int index, int length)  
{  
    int child;  
    int temp = array[index];  
      
    if (2 * index + 1 >= length)  
    {  
        return;  
    }  
  
    //子结点位置 = 2 * 父结点位置 + 1  
    child = 2 * index + 1;  
          
    //得到子结点中较大的结点   
    if (child < length - 1 && array[child + 1] > array[child])  
    {  
        ++child;  
    }  
              
    //如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点   
    if (temp < array[child])  
    {  
        array[index] = array[child];  
    }  
    else  
    {  
        return;  
    }  
          
    //最后把需要调整的元素值放到合适的位置   
    array[child] = temp;  
      
    big_heap_adjust(array, child, length);  
}  
  
/***************************************************************************** 
 函 数 名  : find_kmax_value 
 功能描述  : 查找数组中第K大元素  
 输入参数  : array  待查询的数组  
             length 数组的长度 
             K      第K大  
 输出参数  : 无 
 返 回 值  : 返回第K大元素  
 修改历史      : 
  1.日    期   : 2012/09/10 
    作    者   : liguangting 
    修改内容   :  
*****************************************************************************/  
int find_kmax_value(int *array, int length, int k)  
{  
    int i = 0;  
      
    //把子数组array[0...length-1]构造成大顶堆   
    for (i = length / 2 - 1; i >= 0; i--)  
    {  
        big_heap_adjust(array, i, length);  
    }  
      
    //从最后一个元素开始对数组进行调整,不断缩小调整的范围直到第length - k个元素   
    for (i = length - 1; i >= length - k; i--)  
    {  
        //交换第一个元素和当前的最后一个元素,保证当前的最后一个元素在当前数组中是最大的   
        swap(array[0], array[i]);  
          
        //调整完后的第一个元素是当前数组的最大元素   
        big_heap_adjust(array, 0, i);  
    }  
      
    return array[length - k];  
}  

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

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp1、小顶堆:时间复杂度为O(NlogK),额外空间为O(K)。

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp2、大顶堆:时间复杂度为O(KlogN),额外空间为O(N)。

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


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C语言查找数组中第K大的元素
喜欢 (0)
加载中……