在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大元素。具体实现代码如下:
#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; }
       第二种方法:同样是利用堆排序的思想,但采用的是大顶堆,并且结合部分排序的思想。大致思路:首先把数组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]; }
       总结:以上两种方法同样都是用堆排序的思想来查找第K大元素,那到底有何区别呢?我们主要来看一下时空间复杂度:
       1、小顶堆:时间复杂度为O(NlogK),额外空间为O(K)。
       2、大顶堆:时间复杂度为O(KlogN),额外空间为O(N)。
       在数据量不是很大的情况下,可能以上两种方法的差别并不是特别大。但是,当数据量大到一定程度后,两者的差别就非常明显了。例如:一个文件中有100000000个整数,要求找出第10000大元素。用第一种方法的时间复杂度为100000000log10000,额外空间为10000;用第二种方法的时间复杂度为10000log100000000,额外空间为100000000。在这种情况下,需要用哪一种方法就取决于当时的运行环境、时空要求等因素,或者我们再去寻求时空间复杂度更低的方案。