10000个数求第2大的数,不许用排序算法.谁有没有什么好的方法？？

Question

10000个数求第2大的数,不许用排序算法.谁有没有什么好的方法？？
谢谢了

Answer 1

没有其他限制了（时间或空间）？O（n）找出最大数，在O（n）一次找出第二大的数。
如果数据量很大（比如1亿个数） 可以用分制法，每1万分组找出前两个大数，在归并。

Answer 2

遍历一遍就行了int[] all;//10000个数字
int max,max2;//第一大，第二大数字
int v;max = max2 = all[0];
for(int i=1;i<10000;i++){
   v = all[i];
   if(v > max2){
      if(v > max){
          max2 = max;//原来最大值变第二大
          max = v;//最大值更新为当前值
      }
      else
          max2 = v;//当前值为第二大
   }
}
System.out.println("max="+max+",max2="+max2);

Answer 3

修正下max = all[0];
max2 = all[1];
if(max < max2){
   max = all[1];
   max2 = all[0];
}
for(int i=2;i<1000;i++)
....

Answer 4

告诉楼主个简单的办法， 你把这1000个数放到数组中， 然后调Array.sort(), 然后 去第二个数就可以了

Answer 5

更正， 是Arrays.sort(int[]), 是按 升序排列的。所以只需要 取倒数第二个数就可以了。

Answer 6

根据4楼整理的
class T {
  public static void main(String[] args) {
    System.out.println(getSecondMax(new int[] { 1, 3, 5, 7, 9, 2, 4, 6, 8, 10 }));
  }  /**
   * 求整数数组的第2大的数,不许用排序算法
   * 
   * @param nums
   * @return
   */
  public static int getSecondMax(int[] all) {
    int max, max2;// 第一大，第二大数字
    max = all[0];
    max2 = all[1];
    if (max < max2) {
      max = all[1];
      max2 = all[0];
    }
    for (int i = 1; i < all.length; i++) {
      if (all[i] > max2) {
        if (all[i] > max) {
          max2 = max;// 原来最大值变第二大
          max = all[i];// 最大值更新为当前值
        } else
          max2 = all[i];// 当前值为第二大
      }
    }
    return max2;
  }
}

Answer 7

为什么不用TreeSet呢？
Set set = new TreeSet();
set.add(new Integer(first));
set.add(new Integer(second));
..............................int result = ((Integer)set.get(99998)).intValue();  //一共10000个,set自动按照asc有序存储了.第二大的数字自然是倒数第二个了

Answer 8

呵呵，都没有注意一个细节，如果数中有负数呢？显然第二大数就会出错。 int[] all; //10000个数字
int max,max2; //第一大，第二大数字
int v; max  = all[0];
max2 = Integer.MIN_VALUE; // here
for(int i=1;i <10000;i++){
if( all[i]>max){
max = all[i];
}else if(all[i]>max2){
max2 = all[i];
}
}
System.out.println("max="+max+",max2="+max2);

Answer 9

如果数组中有相等的值的话...如.{ 1, 3, 5, 7, 9, 2, 4, 6, 10, 10 }
结果 max=10,max2=10max2 :"咱们一样大，为什么你排在我前面"
max  :"你那个10是雌的，我的是雄的...."修改一下判断 应该就可以了...

Answer 10

public class BigNum {
public static void main(String[] args) {
int[] a = new int[]{1,684,-2,1564,6564,65,465,-465,464874,464874,464874,464874,9874,9546,-54,65,46,568,8,4685,6,8,46,846,8,6,8446,86,46,8,464874};
if(null != a && a.length>2) printTheFirstBigNumAndTheSecondBigNumInIntArray(a);
}

public static void printTheFirstBigNumAndTheSecondBigNumInIntArray(int[] a) {
int fMax = a[0];
int sMax = a[1];

if(fMax < sMax) {
fMax += sMax;
sMax = fMax - sMax;
fMax = fMax - sMax;
}

for(int i=2; i<a.length; i++) {
if(fMax < a[i]) {
if(sMax < fMax) {
sMax = fMax;
}
fMax = a[i];
}else {
if(fMax != a[i] && sMax < a[i]) {
sMax = a[i];
}
}
}
System.out.println("fMax:\t" + fMax + "\nsMax:\t" + sMax);
}
}