苏木三少
错的不是你,而是这个世界。

分治-输出前m大的数

输出前m大的数

问题

给定一个数组包含n个元素,统计前m大的数并且把这m给数从大到小输出。

输入

第一行包含一个整数n,表示数组的大小。n<100000。

第二行包含n个整数,表示数组的元素,整数之间以一个空格分开。每个整数的绝对值不会超过100000000.

第三行包含一个整数m,m<n

输出

从大到小输出前m大的数,每个数一行。

排序后再输出,复杂度O(nlogn)

用分治处理:复杂度(n+mlogm)

思路,

把前m大都弄到数组最右边,然后对这右边m个元素排序,再输出。

关键O(n)时间内实现把前m大的都弄到数组最右边。

引入操作arrangeRigh(k):把数组(或数组的一部分)前k大的懂弄到最右边。

如何将前k大的都弄到最右边

1)、设key=a[0],将key挪到适当位置,使得比key小的元素都在key左边,比key大的元素都在key右边(线性时间完成)

2)、选择数组的前部或后部在进行arrangeRigjt操作

 

代码截图:

 

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
 
using namespace std;
int a[100];
 
void swap(int &a, int &b)
{
    int temp;
    temp = b;
    b = a;
    a = temp;
}
void QuickSort(int a[], int s, int e, int m)
{
    if (s >= e)
        return;
    int k = a[s];
    int i = s, j = e;
    while (i != j)
    {
        if (j > i && a[j] > k)
            j--;
        swap(a[i], a[j]);
        if (j > i && a[i] < k)
            i++;
        swap(a[i], a[j]);
    }
 
    int b = (e - j) + 1; // 判断右边大的数有几个
    if (m > b)           // 若小于m个,在左边再取m-b个
        QuickSort(a, s, i, m - b);
    if (m < b)           // 若大于m个,在右边再去m个
        QuickSort(a, j + 1, e, m);
}
 
int main()
{
    int m,n;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    QuickSort(a, 0, n - 1, m);
    for (int i = n-1; i >= n-m; i--)
        cout << a[i] << ' ';
    cout << endl;
    system("pause");
}
赞(2) 打赏
有问题的朋友随时留言,或者加我为好友。我的QQ是805375353. <<苏木三少博客 » 分治-输出前m大的数

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

十年之约