4.3 输出前m大的数时间复杂度O(n+mlog(m))

小灰灰 2022-05-08 08:54 148阅读 0赞

![70][]

![70 1][]

![70 2][]

#include<iostream>
    using namespace std;
    
    void swapM(int &a, int &b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    int t = 0;
    int n = 9;
    int a[] = {1,4,7,2,5,8,3,6,9};
    //用治处理  O(n+mlog(m))
    //用O(n)把m大个数挪到右边，然后对这m个数排序再输出
    void QuickSort(int a[], int s, int e)
    {
        if(s >= e)
            return;
        int k = a[s];
        int i = s, j = e;
        while(i != j)
        {
            while(j > i && a[j] >= k)
                --j;
            swapM(a[i],a[j]);
            while(i < j && a[i] <= k)
                ++i;
            swapM(a[i],a[j]);
        }
        QuickSort(a,s,i-1);
        QuickSort(a,i+1,e);
    }
    //把数组（或数组的一部分）前k大的都弄到最右边
    void arrangeRight(int *a, int s, int e, int k)
    {
        if(s >= e)
            return;
        if(k == e-s+1)
            return;
        int i = s;
        int j = e;
        int key = a[s];
        while(i != j)
        {
             while(i < j && a[j] >= key)
                 --j;
             swapM(a[i],a[j]);
             while(i < j && a[i] <= key)
                 ++i;
             swapM(a[i],a[j]);
        }
    	cout << e - i + 1 << endl; 
    	cout << "key:" << key << endl;
        //如果右边的数刚好为e-i+1为k个
        for(int i = 0; i < n; ++ i)
        	cout << a[i] << " " ;
    	cout << endl; 
        if(k == e - i + 1)
            return;
        //右边的数大于k个
        else if(k < e - i + 1)
        {
            arrangeRight(a,i+1,e,k);
        }
        //右边的数小于k个，需要左边取出k - (e-i+1)个
        else
        {
             arrangeRight(a,s,i-1,k-e+i-1);
        }
    }
    
    void printM(int *a, int n, int m)
    {
         //O(N)时间内先把m大的都弄到数组最右边
         arrangeRight(a,0,n-1,m);
        //对这m个数排序
        QuickSort(a,n-m,n-1);
        //输出
        while(m--)
        {
            cout << a[--n] << " ";
        }
        cout << endl;
    }
    int main()
    {
        printM(a,n,4);
        system("pause");
        return 0;
    }

![70 3][]

# 7617:输出前k大的数 #

描述

给定一个数组，统计前k大的数并且把这k个数从大到小输出。

输入

第一行包含一个整数n，表示数组的大小。n < 100000。  
第二行包含n个整数，表示数组的元素，整数之间以一个空格分开。每个整数的绝对值不超过100000000。  
第三行包含一个整数k。k < n。

输出

从大到小输出前k大的数，每个数一行。

样例输入

10
    4 5 6 9 8 7 1 2 3 0
    5

样例输出

9
    8
    7
    6
    5

Accept代码：

#include<iostream>
    #define MAXN 100000
    int a[MAXN+10];
    using namespace std;
    
    void swapM(int &a, int &b)
    {
        int tmp = a;
        a = b;
        b = tmp;
    }
    //int t = 0;
    //int n = 9;
    //int a[] = {1,4,7,2,5,8,3,6,9};
    //用治处理  O(n+mlog(m))
    //用O(n)把m大个数挪到右边，然后对这m个数排序再输出
    void QuickSort(int a[], int s, int e)
    {
        if(s >= e)
            return;
        int k = a[s];
        int i = s, j = e;
        while(i != j)
        {
            while(j > i && a[j] >= k)
                --j;
            swapM(a[i],a[j]);
            while(i < j && a[i] <= k)
                ++i;
            swapM(a[i],a[j]);
        }
        QuickSort(a,s,i-1);
        QuickSort(a,i+1,e);
    }
    //把数组（或数组的一部分）前k大的都弄到最右边
    void arrangeRight(int *a, int s, int e, int k)
    {
        if(s >= e)
            return;
        if(k == e-s+1)
            return;
        int i = s;
        int j = e;
        int key = a[s];
        while(i != j)
        {
             while(i < j && a[j] >= key)
                 --j;
             swapM(a[i],a[j]);
             while(i < j && a[i] <= key)
                 ++i;
             swapM(a[i],a[j]);
        }
    //	cout << e - i + 1 << endl; 
    //	cout << "key:" << key << endl;
        //如果右边的数刚好为e-i+1为k个
      //  for(int i = 0; i < n; ++ i)
        //	cout << a[i] << " " ;
    //	cout << endl; 
        if(k == e - i + 1)
            return;
        //右边的数大于k个
        else if(k < e - i + 1)
        {
            arrangeRight(a,i+1,e,k);
        }
        //右边的数小于k个，需要左边取出k - (e-i+1)个
        else
        {
             arrangeRight(a,s,i-1,k-e+i-1);
        }
    }
    
    void printM(int *a, int n, int m)
    {
         //O(N)时间内先把m大的都弄到数组最右边
         arrangeRight(a,0,n-1,m);
        //对这m个数排序
        QuickSort(a,n-m,n-1);
        //输出
        while(m--)
        {
            cout << a[--n] << endl;
        }
       // cout << endl;
    }
    int main()
    {
    	int n;
    	cin >> n;
    	for(int i = 0; i < n; ++i)
    		cin >> a[i];
    	int m;
    	cin >> m;
        printM(a,n,m);
        return 0;
    }

![70 4][]

[70]: /images/20220508/979a6db37d514013bb96d7272755a272.png
[70 1]: /images/20220508/a65e5ad57c0f46e0b222c35ba92c8328.png
[70 2]: /images/20220508/d697ee43b2bd4877a74c890cdcec1d8d.png
[70 3]: /images/20220508/092c20bd765e49dcb5921082b8954914.png
[70 4]: /images/20220508/55215ef007b249ddb2238f818d466b01.png