当前位置: 代码迷 >> J2SE >> 输入随意M个正整数,要求输出N个最大值
  详细解决方案

输入随意M个正整数,要求输出N个最大值

热度:89   发布时间:2016-04-23 21:25:31.0
输入任意M个正整数,要求输出N个最大值
输入任意M个正整数,要求输出N个最大值,其中M和N数量任意,M远大于N?
如输入10?98?46?55?37?87,输出两个最大值为?98?87,?给出更快,更节省内存的算法

------解决方案--------------------
搞个N长的队列,每次输入都和队列中的值比较,最终保存下来的就是最大的N个数
------解决方案--------------------
用一个大小为N的数组 min heap,  每个输入值和最小值比较,小就抛弃,大就替换。这样算法空间复杂度是 O(N),时间复杂度是 O(M*logN)。
------解决方案--------------------
建一个collection,size N,使用comparator重小到大排列,先一次吃进N个数。最小的在位置0。然后后面的数每个都跟位置0的对比,如果大于就把位置0的删掉,插入新数。时间复杂度 N+logM
------解决方案--------------------
如果是面试题的话,首先要回答"建立size=N的大根堆";接下来,面试官会问你有没有更好的方法,你回答"快速选择";然后你给他解释“快速选择”的基本算法与历史来源,面试官会对你刮目相看。

------解决方案--------------------
既然是只选择前几个最大的数那么就没有必要进行排序了,因为最快的比较排序算法下限都是nln(n), 不过楼主可以试下非比较排序,比如计数排序或者桶排序,详细介绍看我的博文http://blog.csdn.net/china_zoujinyong/article/details/16892223
http://blog.csdn.net/china_zoujinyong/article/details/16898707
不过我还是觉得排序是没有必要的,现在给你一个算法,线性的时间复杂度,常数的大小取决于数据
#include <stdio.h>  
#include <time.h>  
#define SWAP(x, y) {int t; t=x; x=y; y=t;}  
int partition(int a[], int p, int r)  
{  
    int x = a[r];  
    int i = p-1, j;  
    for(j = p; j <= r-1; j++)  
    {  
          if(a[j] <= x)  
          {  
                  i++;  
                  SWAP(a[i], a[j]);          
          }        
    }      
    SWAP(a[i+1], a[r]);  
    return i+1;  
}  
  
int randomized_partiton(int a[], int p, int r)  
{  
    int x = rand()%r;  
    int temp;  
    temp = x+p > r ? x: x+p;  
    SWAP(a[temp], a[r]);  
    return partition(a, p, r);          
}  
  
int randomized_select(int a[], int p, int r, int i)  
{  
     int q, k;  
     // 检测程序只有一个元素的情况   
     if(p==r)   
              return a[p];  
     q = randomized_partiton(a, p, r);  
     k = q - p+1;  
     if(i==k)  
             return a[q];  
     else if(i < k)  
          return randomized_select(a, p, q-1, i);  
     else   
          return randomized_select(a, q+1, r, i-k);      
}  
  
int main()  
{  
    int a[10]={3,1,5,7,8,2,4,6,10,9};  
    int x;  
    srand(time(NULL));  
    x = randomized_select(a, 0, 9, 10);  
    printf("%d\n", x);  
    system("pause");      
    return 0;      
}  



C语言写的,楼主改下就可以了
  相关解决方案