【面试题】10000个数字求第二大的数字,不许用排序算法

西夏一品堂 发布于 2015/05/28 10:04
阅读 1K+
收藏 1

10000个数字求第二大的数字,不许用排序算法


求思路

加载中
1
d
de虫子



import java.util.*;

public class Compare{



    public static void main(String[] args) {
        int[] intArray=new int[10];
        Random r=new Random();
        for(int i=0;i<intArray.length;i++){
            intArray[i]=r.nextInt(10000);
            System.out.print(intArray[i]+"   ");
        }

        int maxNum=intArray[0];
        int secMaxNum=0;
        int j=1;
        while(j<intArray.length){
            int temp=intArray[j];
            if(maxNum>temp){
                if(temp>secMaxNum){
                    secMaxNum=temp;
                }
            }else{
                secMaxNum=maxNum;
                maxNum=temp;
            }

            j++;
        }
        Arrays.sort(intArray);
        for(int c:intArray){
            System.out.println(c+" ");
        }

        System.out.println(maxNum+" "+secMaxNum);
    }
}
d
de虫子
回复 @jluflyingz : 我只是随便凑的10000个数字,你管他是不是小于10000,这有影响吗?
jluflyingz
jluflyingz
是10000个数字,数字未必都是小于10000的
1
vvtf
vvtf
public static void max2rd(int len) {
	int[] arr = new int[len];
	int[] max = new int[2];
	for(int i = 0; i < len; arr[i ++] = new Random().nextInt(1777));
	for(int num : arr) {
		System.out.print(num + ",");
		if(num > max[1] && num < max[0]) max[1] = num;
		if(num > max[0]) {
			int tmp = max[0];
			max[0] = num;
			max[1] = tmp;
		}
	}
	System.out.println();
	System.out.println("Max1st = " + max[0]);
	System.out.println("Max2rd = " + max[1]);
}



1
orangleliu
orangleliu
循环一边不就好了。。
1
plumshop
plumshop
max1=0;//存最大
max2=0; //存次大;仅是算法,暂考虑非负值。
if(x>max1){
    max2=max1;max1=x;
}elseif(max1>x and x>max2){
    max2=x;
}
0
独孤伊

求两次最大值, 第一次找到最大的,然后把它移除,再找最大值就是第二大的


十月阳光
十月阳光
+1024
0
s
scnu_lying

平衡二叉树可以解决,一边读一边插入,左孩子<父节点 右孩子>父节点

插完后右边的最后一个父节点就是第二大了

十月阳光
十月阳光
好高大上,完全不理解树,当初学数据结构的时候酱油打满了
jluflyingz
jluflyingz
正解!
0
安西都护府首席程序员
安西都护府首席程序员
int max=arr[0];//表示为最大
int maxindex=0;//表示最大的索引
int ded=arr[0];
for(int i=1;i<arr.length;i++){
if(arr[i]>max){
maxindex=i;
max=arr[i];
}
}
//第一遍找到最大的数

//第二遍找第二大的数,如果遇到最大的索引就略过
for(int i=1;i<arr.length;i++){
if(i==maxindex)
continue;
if(arr[i]>ded)
ded=arr[i];

}
hmh
hmh
有问题,如果有两个相同的最大值就出错了!
西夏一品堂
西夏一品堂
两次循环,效率不高
0
s
scnu_lying

想了想,我刚方法不对,平衡二叉树目的是查找,按我那个方法 比较的次数大大增加

具体方法应该是楼下的,按顺序,一个个比,设置好当前最大值和当前第二大值

0
hmh
hmh
var a = [];//10000个数字
var m1 = 0,m2 = 0; 
a.forEach(function(val, index){
    if(val > m1){
        if(m1 > m2) m2 = m1;
        m1 = val;
    }else if(val > m2){
        m2 = val;
    }
})
console.log(m1, m2);



hmh
hmh
回复 @君子常当当 : 不对,应该是要判断a[0] 和 a[1] 谁大, 大的放在m1, 小的放在m2
君子常当当
m1=a[1];m2=a[1]; 是不是好些
hmh
hmh
回复 @Transy : 我看错了你的回答,不好意思。。。
T
Transy
@hmh 题目没有说数字全部大于0
T
Transy
这个有bug,当所有数字都小于0的时候
0
edi
edi
一次循环 两次比较
返回顶部
顶部