智力面试题

Question

给定1000个整数，不准用排序算法，如何得到第二大的数？谢谢，请给出具体的程序代码。

Answer 1

private static int getSecMaxNum(int[] array) {
int SecMaxNum = 0;
if (array.length == 0 ) {
SecMaxNum = -1;
}
if (array.length == 1) {
SecMaxNum = array[0];
} if (array.length == 2) {
SecMaxNum = Math.min(array[0], array[1]);
}
if (array.length >= 3) {
int tempMax = Math.max(array[0], array[1]);
int tempSecMax = Math.min(array[0], array[1]);

for (int i = 2; i < array.length; i++) {
System.out.println("1");
if (array[i] > tempMax) {
System.out.println("2");
tempSecMax=tempMax;
tempMax = array[i];
} else if (array[i] > tempSecMax) {
System.out.println("3");
tempSecMax = array[i];
} else {
continue;
}
}
SecMaxNum = tempSecMax;
}
return SecMaxNum;
}

Answer 2

public class TestSecond { public static void main(String[] args) {
int[] arr = {4,4,7,8,68,5,10,34,56,55,78,23,89};
System.out.println(getSecond(arr));
}

static int getSecond(int[] arr){
int len = arr.length;
if(len < 1){
System.out.println("数组的长度应不少于2");
return -1;
}
int max = arr[0] > arr[1] ? arr[0] : arr[1];
int sec = arr[0] < arr[1] ? arr[0] : arr[1];
int temp = 0;
for(int i = 1; i < len; i++){
if(arr[i] > max){
temp = max;
max = arr[i];
sec = temp;
}else if(arr[i] > sec){
sec = arr[i];
}
}
return sec;
}
}
没有考虑第一大与第二大的一样的...

Answer 3

时间复杂度应该在 o(n) 
另取两个临时变量，保存 max 1, max 2
再一次次比较

Answer 4

import java.util.Arrays;
import java.util.Random;public class Test {    public static void main(String[] args) {        int[] testNum = randoms(10000, 100);        int maxNum = testNum[0]; // 记录初始最大的数
        int secondMaxNum = testNum[1]; // 记录初始第二大的数
        if (secondMaxNum > maxNum) { // 比较互换
            int temp = secondMaxNum;
            secondMaxNum = maxNum;
            maxNum = temp;
        }        int nowNum = 0;// 记录当前比较的数
        for (int i = 2; i < testNum.length; i++) {
            nowNum = testNum[i];
            // 如果当前的数大于最大值，则赋第二大值为原最大值，最大值为当前值
            if (nowNum > maxNum) {
                secondMaxNum = maxNum;
                maxNum = nowNum;
            } else if (nowNum > secondMaxNum) {
                // 如果不大于最大值但大于第二大值，则第二大值取当前值
                secondMaxNum = nowNum;
            }
        }
        System.out.println("第二大值:" + secondMaxNum);
        // 对原数组进行排序显示，用于比对测试结果
        Arrays.sort(testNum);
        for (int i = 0; i < testNum.length; i++) {
            if (i % 10 == 0) {
                System.out.println();
            }
            System.out.print(testNum[i] + "\t");
        }    }    /**
     * 从指定的范围，生成指定个数的不重复的随机数组
     * @param sumNum　范围
     * @param num　个数
     * @return　取得的随机数
     */
    public static int[] randoms(int sumNum, int num) {
        int returnValue[] = null;
        if (num <= sumNum) {
            returnValue = new int[num];
            Random r = new Random();            int temp1, temp2;
            // 生成范围数组
            int send[] = new int[sumNum];
            int len = send.length;
            for (int i = 0; i < len; i++) {
                send[i] = i + 1;
            }            for (int i = 0; i < num; i++) {
                temp1 = Math.abs(r.nextInt()) % len;
                returnValue[i] = send[temp1];
                temp2 = send[temp1];
                send[temp1] = send[len - 1];
                send[len - 1] = temp2;
                len--;
            }
        }
        return returnValue;
    }}

Answer 5

import java.util.Arrays;public class TestSecMaxShow { public static int findSecMax(int[] a,int start,int end){
if(start<0||end<0){
System.out.println("start and end is not valified!");
return -1;
}
if(start==end){
return a[start];
}
int[] array = Arrays.copyOfRange(a, start, end);
if(array==null||array.length<1){
return -1;
}else if(array.length==1){
return array[0];
}else if(array.length==2){
return array[0]>array[1]?array[1]:array[0];
}else{
int secMaxLeft = findSecMax(array,0,array.length/2);
int secMaxRight = findSecMax(array,array.length/2,array.length); 
return secMaxLeft > secMaxRight ? secMaxLeft : secMaxRight;
}
}
public static void main(String[] args) {
int[] a = new int[]{1,2,3,4,5,6,7,8,9,10};
System.out.println(findSecMax(a,0,a.length));
}}

Answer 6

粗略找3个方法，还是loop最快
public class NumberScale { /**
 * 最没必要
 * @param index
 * @param nums
 * @param biggest
 * @param second
 * @return
 */
public static int recursionBigger(int index, int[] nums, int biggest, int second) {
if(index >= nums.length) {
return second;
}

int current = nums[index++];

if(current > biggest) {
second = biggest;
biggest = current;
} else if(current > second) {
second = current;
}

return recursionBigger(index, nums, biggest, second);
}

/**
 * 速度最快
 * @param nums
 * @return
 */
public static int loopBigger(int[] nums) {
int biggest= nums[0] > nums[1]?nums[0]:nums[1];
int second = nums[0] <= nums[1]?nums[0]:nums[1];

for(int i = 2; i < nums.length; i ++) {
if(nums[i] > biggest) {
second = biggest;
biggest = nums[i];
} else if(nums[i] > second) {
second = nums[i];
}
}

return second;
}

/**
 * 代码最少
 * @param nums
 * @return
 */
public static int sortBigger(int[] nums){ 
Arrays.sort(nums);

return nums[nums.length - 2];
}

public static void main(String[] args) {
int [] array = {3, 18, 29, 1, 48, 9234, 1133, 724, 241, 7163};


int nums[] = new int[20000];
for(int i = 0; i < 20000; i ++) {
int num = (int)(Math.random() * 1000000000) - 10000;
nums[i] = num;
}

nums[183] = 999;

long before = new Date().getTime();
int biggest = sortBigger(nums);
long after = new Date().getTime();
long spent = after - before;
System.out.println("Sorting second big is: \t\t" + biggest + "[time:" + spent + " ms]");

before = new Date().getTime(); 
biggest = loopBigger(nums);
after = new Date().getTime();
spent = after - before;
System.out.println("Loop second big is: \t\t" + biggest + "[time:" + spent + " ms]");
int max= nums[0] > nums[1]?nums[0]:nums[1];
int sec = nums[0] <= nums[1]?nums[0]:nums[1];

before = new Date().getTime();
biggest = recursionBigger(2, nums, max, sec);
after = new Date().getTime();
spent = after - before;
System.out.println("Recursion second big is: \t" + biggest + "[time:" + spent + " ms]");
}
}
2万个整数里搜索第二大数测试结果：Sorting second big is:  999942921[time:23 ms]
Loop second big is:  999942921[time:1 ms]
Recursion second big is:  999942921[time:2 ms]

Answer 7

Binary Search 二分法查找如何？

Answer 8

真下功夫啊.循环和递归都是o(n)，排序是n*log(n)的，当然不能用排序。同样的问题，递归要比循环慢，递归至少要消耗一些时间用来做进栈和出栈操作。像求fibonacci数列用递归，那就还有大量的重复计算，效率坏极了。

Answer 9

public class TestSecond {
public static void main(String args[]){
int a[] = {13,523,-6,635,234,-32,5,562,23,65};
int max = a[0],index = 0;
int i = 1;
for(; i < a.length; i++)
if(a[i] > max){
max = a[i];
index = i;
}
if(index == a.length - 1)
a[index] = Integer.MIN_VALUE;
else
for(int j = index; j < a.length - 1; j++)
a[j] = a[j + 1];

max = a[0];
for(i = 1; i < a.length; i++)
if(a[i] > max)
max = a[i];
System.out.println("The second max number is :" + max);
}

}

Answer 10

用java Array.sort() 第二个值就是