胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。
输入首先给出两个正整数N（≤10
6
）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。
在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。
8 3
8 12 7 3 20 9 5 18
20 18 12
 
 
用归并排序做的，用快速排序做最后一个点超时
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define MAX_SIZE 1100000                
  4. int a[MAX_SIZE];                //因为MAX_SIZE 太大，所以数组要定义在函数以外
  5. int temp[MAX_SIZE];         //中间数组，用完后赋值给原数组
  6. int merging(int* list1,int list1_size,int *list2,int list2_size)
  7. {
  8.     int i=0,j=0,k=0;
  9.     while(i<list1_size&&j<list2_size)   //线性表的merge排序操作，merge的意思是融入
  10.     {
  11.         if(list1[i]<list2[j])
  12.         {
  13.             temp[k++]=list1[i++];       //注意不要漏掉里面的++
  14.         }
  15.         else
  16.         {
  17.             temp[k++]=list2[j++];
  18.         }
  19.     }
  20.     while(i<list1_size)
  21.     {
  22.         temp[k++]=list1[i++];
  23.     }
  24.     while(j<list2_size)
  25.     {
  26.         temp[k++]=list2[j++];
  27.     }
  28.     for(i=0;i<list1_size+list2_size;i++)        //赋值给原数组
  29.     {
  30.         list1[i]=temp[i];
  31.     }
  32.     return 0;
  33. }
  35. int MergeSort(int *a,int n)
  36. {
  37.     if(n>1)
  38.     {
  39.         int *list1=a;
  40.         int list1_size=n/2;
  41.         int *list2=a+list1_size;
  42.         int list2_size=n-list1_size;
  43.         MergeSort(list1,list1_size);    //递归左边的数组，对半分
  44.         MergeSort(list2,list2_size);    //递归右边的数组，对半分，因为对半分的，所以时间复杂度为log（n）
  46.         merging(list1,list1_size,list2,list2_size); //合的操作，将左右有序的合为一个数组
  48.     }
  49.     return 0;
  50. }
  52. int main()
  53. {
  54.     int n,m;
  55.     scanf("%d%d",&n,&m);
  56.     int i,flag=0;
  57.     for(i=0;i<n;i++)
  58.     {
  59.        scanf("%d",&a[i]);
  60.     }
  61.     MergeSort(a,n);
  62.     if(n>m)                //---这里加一个判断，n与m不一定谁大，不然有一个点过不了
  63.     {
  64.         for(i=n-1;i>=n-m;i--)
  65.         {
  66.             if(flag==1)printf(" ");flag=1;
  67.             printf("%d",a[i]);
  68.         }
  69.     }
  70.     else
  71.     {
  72.         for(i=n-1;i>=0;i--)
  73.         {
  74.             if(flag==1)printf(" ");flag=1;
  75.             printf("%d",a[i]);
  76.         }
  77.     }
  78.     return 0;
  79. }

 

版权声明：本文为Orzsl原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Orzsl/p/10041920.html