编程之美：寻找最大的K个数

川长思鸟来 2022-06-04 08:17 202阅读 0赞

### 解法一： ###

> 该解法是大部分能想到的，也是第一想到的方法。假设数据量不大，可以先用快速排序或堆排序，他们的平均时间复杂度为O(N\*logN),然后取出前K个，时间复杂度为O(K)，总的时间复杂度为O(N\*logN)+O(K).
> 
> 当K=1时，上面的算法的时间复杂度也是O(N\*logN)，上面的算法是把整个数组都进行了排序，而原题目只要求最大的K个数，并不需要前K个数有限，也不需要后N-K个数有序。可以通过部分排序算法如选择排序和交换排序，把N个数中的前K个数排序出来，复杂度为O(N\*K),选择哪一个，取决于K的大小，在K(K

### 解法二： ###

> 避免对前K个数进行排序来获取更好的性能(利用快速排序的原理)。  
> 假设N个数存储在数组S中，从数组中随机找一个元素X，将数组分成两部分Sa和Sb.Sa中的元素大于等于X,Sb中的元素小于X。  
> 出现如下两种情况：  
> (1)若Sa组的个数大于或等于K，则继续在sa分组中找取最大的K个数字 。  
> (2)若Sa组中的数字小于K ，其个数为T，则继续在sb中找取 K-T个数字 。  
> 一直这样递归下去，不断把问题分解成小问题，平均时间复杂度为O(N\*logK)。

就是算法导论中选择算法：[http://blog.csdn.net/u013948010/article/details/78749809][http_blog.csdn.net_u013948010_article_details_78749809]

### 解法三： ###

> 用容量为K的最小堆来存储最大的K个数。最小堆的堆顶元素就是最大K个数中的最小的一个。每次扫描一个数据X，如果X比堆顶元素Y小，则不需要改变原来的堆。如果X比堆顶元素大，那么用X替换堆顶元素Y，在替换之后，X可能破坏了最小堆的结构，需要调整堆来维持堆的性质。调整过程时间复杂度为O(logK)。 全部的时间复杂度为O(N\*logK)。数据量大时适用。

先实现调整小顶堆和建立小顶堆的函数：

/*调整小根堆*/
    void min_heapify(int data[], int cur, int heapsize)
    {
        int left = 2 * cur + 1;
        int right = left + 1;
        int smallest = cur;
        if (left<heapsize && data[left] < data[smallest]) {
            smallest = left; //最大为左子树
        }
        if (right<heapsize && data[right] < data[smallest]) {
            smallest = right;//最大为右子树
        }
        if (smallest != cur) //根不是最小，则要交换
        {
            int temp = data[cur];
            data[cur] = data[smallest];
            data[smallest] = temp;
            min_heapify(data, smallest, heapsize); //继续调整
        }
    }
    /*建立小根堆*/
    void build_min_heap(int data[], int heapsize)
    {
        for (int i = heapsize / 2 - 1; i >= 0; i--) {
            min_heapify(data, i, heapsize);
        }
    }

再实现维护大小为k的小顶堆，并遍历数组不断调整堆

//寻找数组最大的k个元素，heap的大小为k
    void heap_selectk(int array[],int k,int size,int heap[]) {
        for (int i = 0; i < k; i++) {
            heap[i] = array[i];
        }
        build_min_heap(heap, k);    //初始化小顶堆
        for (int i = k; i < size; i++)
        {
            if (array[i] > heap[0]) //数组元素小于堆顶
            {
                heap[0] = array[i];
                min_heapify(heap, 0, k);
            }
        }
    }

输出的heap数组就是最大的k个元素,测试

int main()
    {
        int array[6] = { 4,7,1,2,0,9 };
        int heap[3];
        heap_selectk(array, 3, 6, heap);
        cout << "寻找后:";
        for (int i = 0; i < 3; i++) {
            cout << heap[i] << " ";
        }
    }

> 输出：  
> 寻找后：4 7 9

[http_blog.csdn.net_u013948010_article_details_78749809]: http://blog.csdn.net/u013948010/article/details/78749809