求数组中n个最大的算法（只给最佳答案50分）

public int[] maxN(int n, int[] a) {
int[] temp = new int[n];
int max;
int pos;
for(int i=n-1; i>=0; i--) {
pos = 0;//假设最大的值位于第0个位置
max = a[0];
for(int j=0; j<a.length; j++) {
//找出最大的一个数，并记录其对应的下标
if(a[j] > max) {
max = a[j];
pos = j;
}
}
temp[i] = max;//把最大的一个存入数组
a[pos] = Integer.MIN_VALUE;//修改原值最大的位置的值为最小
}
return temp;
}

public static void main(String[] args){
Integer i[] = {11,33,100,200,500,100,465,132, 464,489,156,789};
int n = 5;
List<Integer> il = new ArrayList(Arrays.asList(i));
while (il.size() > n){
il.remove((Integer)min(il.subList(0, n)));
}
System.out.println(il);
}

public static int min(List<Integer> il){
int i = il.get(0);
for (Integer I:il){
if (i > I) i = I;
}
return i;
}

一次循环搞定
public int[] maxN(int n, int[] a) {
        int[] temp = new int[n];        int minIndex=0;  //在已选中最小的index        for (int i=0;i<a.length;i++){
           if (i<=n) {
              temp[i]=a[i];
              if (temp[minIndex]>a[i])  minIndex=i;
           }else {
             if (a[i]>temp[minIndex]) {
               temp[minIndex]=a[i];
               minIndex=resetMin(temp);
             }
           }
        }
        return temp;
    }public int resetMin(int[] temp){  //在已选的结果里找最小的
   int minIndex=0;
   for (int i=1;i<temp.length;i++){
       if (temp[minIndex]>temp[i]) minIndex=i;
   }
   return minIndex;
}

public int[] maxN(int n, int[] a){
int [] t = new int[n];
TreeSet<Integer> tree = new TreeSet<Integer>();
tree.add(a[0]);
for(int i=1;i<a.length;i++){
if(tree.first() < a[i]){
tree.add(a[i]);
if(tree.size()>n){
tree.remove(tree.first());
}
}
}
Iterator<Integer> iter = tree.iterator();
for(int i=0;i<n;i++){
if(iter.hasNext())
t[i] = iter.next();
}
return t;
}

public int[] maxN(int n, int[] a) {
if (a == null || a.length == 0 || n < 1) {
return null; // return new int[0]; 也可以
}
int[] ret = new int[n];
int retLen = ret.length;
int index = a.length - retLen;
// 从小到大排序
Arrays.sort(a);
// 循环赋值,随后n个
for (int i = 0; i < retLen; i++) {
ret[i] = a[index + i];
}
return ret;
}a

简化下:
public int[] maxN(int n, int[] a) {
if (a == null || a.length == 0 || n < 1) {
return null; // return new int[0]; 也可以
}
Arrays.sort(a);
return Arrays.copyOfRange(a, a.length - n, a.length);
}

结果是对的，不过最后的结果还是没有按照原来的顺序取出最大的数，比较替换的时候乱掉了public int[] maxN(int n, int[] a){
        int[] b = new int[n];
        int index = -1,temp = 0;
        System.arraycopy(a, 0, b, 0, n);
        for(int i = n; i < a.length; i++) {
         temp = a[i];
         for(int j = 0; j < n; j ++) {
         if(temp > b[j]) {
         temp = b[j];
         index = j;
         continue;
         }
         }
         if(index != -1)
         b[index] = a[i];
         index = -1;
        }
        return b;
    }

假设数组长度为 M 找前 N 大的数
1. 常规算法
读一遍数组往一个长度为 N 的数组里插边插入边排序
时间复杂度为 O(M * N)
2. 如果本题中的数字都不是很大的话，可以利用空间换时间的想法
以参数数组中的数为下标建立一个boolean数组，数组长度为参数数组中最大的值
最后顺序读一遍就可以得出前N大的数；
时间复杂度为O（M）；
3.如果数组中数字比较大但 M 不是非常大
就可以利用快排的思想
那样的话时间复杂度为 O(M * log K)
4.如果数组长度非常大，如几千亿，那样的话内存是不够的
这个时候就要用容量为 N 的最小堆来存储最大的 N 个数。
时间复杂度为 O(M * log K)

刚写了下，用的是我在 13 楼说的第 4 种方法
这个方法返回的数是最大的 N 个数，但是是未排序的public class Test { public static void main(String[] args) {
int n = 7;
int[] a = { 5, 7, 1, 55, 22, 56, 7723, 54, 563123, 6435, 1525334523, 54323, 564545, 335,23452345 };
int[] result = maxN(n, a);
for (int i = 0; i < result.length; i++) {
System.out.printf("%d ", result[i]);
}
} public static int[] maxN(int n, int[] a) {
//用一个数组模拟完全2叉树，节点 N 的左子节点为 2 * N + 1，右子节点为 2 * N + 2；
//最小堆中任意一个节点的值小于自己的子节点
int[] result = new int[n];
int p, q;
for (int i = 0; i < a.length; i++) {
//从数组中读的数大于最小堆中的最小值（树的根）
if(a[i] > result[0]){
result[0] = a[i];
p = 0;
//维护树的特性
while(p < result.length){
q = 2 * p + 1;
if(q >= result.length)
break;
if((q < result.length - 1 && (result[q + 1] < result[q])))
q = q + 1;
//如果某一节点的值大于其子节点的最小值，将其交换
if(result[q] < result[p]){
result[q] ^= result[p];
result[p] ^= result[q];
result[q] ^= result[p];
p = q;
}else{
break;
}
}
}
}
return result;
}
}
测试结果：
6435 7723 54323 1525334523 563123 564545 23452345

int n=3;
Integer[] a={5,7,1,55,22,56,77,-2};
TreeSet<Integer> ts = new TreeSet();
ts.addAll(Arrays.asList(a));
for(int i=0;i<n;i++){
System.out.println(ts.pollLast());//求最大
// System.out.println(ts.pollFirst());//求最小
}
用了TreeSet使得它可以自动排序，不知道是否符合LZ的要求

public int[] maxN(int n, int[] a){......
     TreeSet<Integer> ts = new TreeSet();
ts.addAll(Arrays.asList(a));
for(int i=0;i<a.length-n;i++){
ts.pollFirst();
}
Integer[] b = new Integer[n];
ts.toArray(b);
System.out.println(Arrays.asList(b));
        return b;
}

int[] getMax(int[] source ,int index){
int[] result=new int[index];
int max=index-1;
for(int i=0,len=source.length;i<len;i++){
int now=source[i];
int j=0;
for(;j<index&&j<i;j++){
if(result[j]<=now){
for(int k=max;k>j;k--){
result[k]=result[k-1];
}
break;
}
}
if(j<index)
result[j]=now;
}
return result;
}

我用10万条数据取前5万大的数作效率测试的话，
keeya0416很快，但是结果不对。
hudie1234567很慢，但是结果对。

把前 n 个数直接默认为最大的，
然后对这个 n个数进行排序，
后面的数字只要和 n 里面最大的和最小的进行比较就行。

到目前为止好像我在4楼发布的算法最好，但其中有个小失误，下面改正了：  public int[] maxN(int n, int[] a) {
    int[] temp = new int[n];    int minIndex = 0; //在已选中最小的index    for (int i = 0; i < a.length; i++) {
      if (i < n) {//4楼这里是(i<=n),这里改正了
        temp[i] = a[i];
        if (temp[minIndex] > a[i])
          minIndex = i;
      }
      else {
        if (a[i] > temp[minIndex]) {
          temp[minIndex] = a[i];
          minIndex = resetMin(temp);
        }
      }
    }
    return temp;
  }  public int resetMin(int[] temp) { //在已选的结果里找最小的
    int minIndex = 0;
    for (int i = 1; i < temp.length; i++) {
      if (temp[minIndex] > temp[i])
        minIndex = i;
    }
    return minIndex;
  }

你的时间复杂度比较高是 O（m * n）的
这个题可以做到 O（m * log n）的

我用10万条数据取前5万大的数作效率测试的话，lxpstart才用了4秒多。
不过前面CoderPlusPlus和hardycheng说得也对，如果lxpstart算法里面的resetMin用堆可能还能更快。

刚才算了下
如果lxpstart算法里面的resetMin用堆的话速度可以再提高 3000 多倍左右
log（2,50000） < 16

sorry, keeya0416是堆王：10万条数据取前5万大的数作效率测试，用了<0.01秒。

sorry。是我搞错了，你的heap太帅了:)

LZ 的意思是别把参数数组排序了再取前 N 个呵呵

请试一试我的程序:
int[] getMax(int[] source ,int index){
int[] result=new int[index];
int max=index-1;
for(int i=0,len=source.length;i<len;i++){
int now=source[i];
int j=0;
for(;j<index&&j<i;j++){
if(result[j]<now){
for(int k=max;k>j;k--){
result[k]=result[k-1];
}
break;
}
}
if(j<index)
result[j]=now;
}
return result;
}

lliiqiang的算法用了14秒（top 50k in 100k）

用Random.nextInt()来填充；用System.currentTimeMillis()来计时。

en
14楼的算法确实没什么好说的，佩服，楼主怎么还不给分
还有不知道你为什么抵触排序，其实
Arrays.sort+Arrays.copyOfRange效率也非常高
今天再次再次实验
在n比较接近m时甚至超过14楼的算法

14楼的算法对？
如果输入的数组都是负数，这个能给你返回全0，呵呵
如果要用这个算法，至少先找最小值，把result[]全部初始化为最小值

我承认14楼的算法效率最高，但是有个小缺点，考虑不周，我给改一下，就perfect了    public static int[] maxN(int n, int[] a) {
        //用一个数组模拟完全2叉树，节点 N 的左子节点为 2 * N + 1，右子节点为 2 * N + 2；
        //最小堆中任意一个节点的值小于自己的子节点
        int[] result = new int[n];
        int p, q;
        int l=0;//堆的已有长度        for (int i = 0; i < a.length; i++) {
            //这里我改成如如果堆未满，就填堆，如果堆满了，就和堆中的最小值（树的根）比较
            if(a[i] > result[0]||l<n){
                if (l<n){
                  result[l]=a[i];
                  l++;
                }else
                  result[0] = a[i];
                p = 0;
                //维护树的特性
                while(p < result.length){
                    q = 2 * p + 1;
                    if(q >= result.length)
                        break;
                    if((q < result.length - 1 && (result[q + 1] < result[q])))
                        q = q + 1;
                    //如果某一节点的值大于其子节点的最小值，将其交换
                    if(result[q] < result[p]){
                        result[q] ^= result[p];
                        result[p] ^= result[q];
                        result[q] ^= result[p];
                        p = q;
                    }else{
                        break;
                    }
                }
            }
        }
        return result;
    }

不好意思，敢发出就发现我加了个
int l=0;//堆的已有长度
简直是脱了裤子放屁，因为l和i是同步的,所以不加这个变量程序更简洁：public static int[] maxN(int n, int[] a) {
        //用一个数组模拟完全2叉树，节点 N 的左子节点为 2 * N + 1，右子节点为 2 * N + 2；
        //最小堆中任意一个节点的值小于自己的子节点
        int[] result = new int[n];
        int p, q;
        for (int i = 0; i < a.length; i++) {
            //这里我改成如如果堆未满，就填堆，如果堆满了，就和堆中的最小值（树的根）比较
            if(a[i] > result[0]||i<n){
                if (i<n){
                  result[i]=a[i];
                  l++;
                }else
                  result[0] = a[i];
                p = 0;
                //维护树的特性
                while(p < result.length){
                    q = 2 * p + 1;
                    if(q >= result.length)
                        break;
                    if((q < result.length - 1 && (result[q + 1] < result[q])))
                        q = q + 1;
                    //如果某一节点的值大于其子节点的最小值，将其交换
                    if(result[q] < result[p]){
                        result[q] ^= result[p];
                        result[p] ^= result[q];
                        result[q] ^= result[p];
                        p = q;
                    }else{
                        break;
                    }
                }
            }
        }
        return result;
    }

JAVA编程思想里有完整的思想+例子，虽然有点出入，但差不多

仔细看了一下，上面的算法都有问题，14楼的算法虽然效率最高，但有错：如果输入数组有负数就不能出正确结果，就算输入数组都大于0，它也不一定正确，没有考虑其中某些数相等的情况，例如在｛1，2，2，3｝里选3个，它会选出｛1，2，3｝。
我在49楼的改进版也有问题，添加节点不是那样加的，最终改正如下：public class Test {    public static void main(String[] args) {
        int n = 50000;
        int[] a = new int[100000];
        //初始化数组为随机产生的-10000000~10000000的整数
        for (int i=0;i<100000;i++) a[i]=(int)((Math.random()-0.5)*20000000);
        java.util.Date d1=new java.util.Date();
        int[] result = maxN(n, a);
        java.util.Date d2=new java.util.Date();
        System.out.println("用了"+(d2.getTime()-d1.getTime())+"毫秒");
        System.out.println("已选最小的是"+result[0]);
        int mc=0;
        int ec=0;
        for (int i=0;i<100000;i++){
          if (a[i]<result[0]) mc++;
          else if (a[i]==result[0]) ec++;
        }
        System.out.println("小于它的有"+mc+"个");
        System.out.println("等于它的有"+ec+"个");
        if (mc<=50000&&mc+ec>50000){
          System.out.println("算法成功！");
        }else{
          System.out.println("算法失败！");
        }
    }    public static int[] maxN(int n, int[] a) {
         //用一个数组模拟完全2叉树，节点 N 的左子节点为 2 * N + 1，右子节点为 2 * N + 2；
         //最小堆中任意一个节点的值小于自己的子节点
         int[] result = new int[n];
         int p, q;
         int value;         for (int i = 0; i < a.length; i++) {
           if(i<n){
                  result[i]=a[i];//添加节点
                  //把新加的节点放到应该放的位置
                  p=i;
                  while (p>0){
                    //如果小于父节点就交换
                    q=(p-1) / 2;
                    if (result[p]<result[q]){
                      result[q] ^= result[p];
                      result[p] ^= result[q];
                      result[q] ^= result[p];
                      p = q;
                    }
                    else {
                      break;
                    }
                  }
                }
              else if (a[i]>result[0]){
                  result[0] = a[i];
                  //维护树的特性
                  p = 0;                  while (p < result.length) {
                    q = 2 * p + 1;
                    if (q >= result.length)
                      break;
                    if ( (q < result.length - 1 && (result[q + 1] < result[q])))
                      q = q + 1;
                      //如果某一节点的值大于其子节点的最小值，将其交换
                    if (result[q] < result[p]) {
                      result[q] ^= result[p];
                      result[p] ^= result[q];
                      result[q] ^= result[p];
                      p = q;
                    }
                    else {
                      break;
                    }
                  }
                }
         }
         return result;
     }
}

我改进了我的算法：
不过我的结果数组中最后一个元素是无效的
private static int[] getMax(int[] source, int index) {
int[] result = new int[index + 1];
for (int i = 0, len = source.length; i < len; i++) {
int now = source[i];
int j = Math.min(index, i);
for (; j > 0; j--) {
int the = result[j - 1];
if (now > the)
result[j] = the;
else
break;
}
result[j] = now;
}
return result;
}

调试易

求数组中n个最大的算法（只给最佳答案50分）

解决方案 »