10000个数求第2大的数,不许用排序算法.谁有没有什么好的方法？？
谢谢了
------解决方案--------------------
没有其他限制了（时间或空间）？O（n）找出最大数，在O（n）一次找出第二大的数。
如果数据量很大（比如1亿个数） 可以用分制法，每1万分组找出前两个大数，在归并。
------解决方案--------------------
o(n)一次就够了
每次保留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);
------解决方案--------------------
根据4楼整理的
- Java code
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; }}
------解决方案--------------------
- Java code
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);
}
}