从数组中获得最大值和次大值，这是个公司的面试题目，本人开始觉得排个序就Ok了，可是一想既然是面试肯定不会这么简单。想了老一会，有了一个想法，定义两个变量x,y，x和y大小开始都为数组第一个值，遍历数组，和x经过比较，如果比较的数大于x，那么x就赋值给y，大于x的数赋值给x，直到最后，比较完，x中存放的是最大值，y中存放的就是最小值。

这种思路可以解答，有没有更简单一些的方法呢？求牛人解答！{:soso_e189:}

王靖远 发表于 2013-7-5 20:31
Arrays.sort(arr);
int max = arr[arr.length]

嘿嘿 没注意。

宋旭东 发表于 2013-7-5 22:39
我问的是最大值和次大值问题，不是单纯的最值。

Arrays.sort(arr)排序 这难道不是最简答的排序？
arr[arr.length-1]最大值
arr9arr.length-20不就是次大值吗？
我这个思路5秒钟就能搞定。快速解决问题不就是最重要的吗

你的实现似乎有几个问题，你那个y里面存的既不是最小值，也不是次大值，只是最大值之前的次大值，比如一个数组{1,5,4,3,2}，那么你的最大值等于5，次大值将等于1。

还有一种情况，如果数组第一个值就是最大值，比如{5,4,3,2,1}，那么你的最大值和次大值将都是5。

要我说最简单的就冒泡排序只跑2趟，arr.lenth * 2 - 3次比较就冒出最大值和次大值了。屌丝解法。

或者这样：

1. class MaxSec
   
2. {
   
3.         public static void main(String[] args)
   
4.         {
   
5.                 int[] arr = new int[]{100,3,2,5,23,6,7,34,5,25,8,1000};
   
6.                 int max = arr[0], sec = Integer.MIN_VALUE;
   
7.                 for(int i = 1; i < arr.length; i++){
   
8.                         if (sec <= arr[i])
   
9.                         {
   
10.                                 if (max <= arr[i])
    
11.                                 {
    
12.                                         sec = max;
    
13.                                         max = arr[i];
    
14.                                 }
    
15.                                 else
    
16.                                         sec = arr[i];
    
17.                         }
    
18.                 }
    
19.                 System.out.println(max + ", " + sec);
    
20.         }
    
21. }
    

复制代码

这样只要不是升序数组，总会比用两趟的冒泡少比较几次。

至于再高端的算法嘛，本屌不会了{:soso_e154:}

可以用递归算法，就是把数组二等分，找出每一段的最大值，就这样逐次递归。最后会有两个最大值，这两个值肯定是最大值和次大值。

王靖远 发表于 2013-7-5 20:31
Arrays.sort(arr);
int max = arr[arr.length]

我问的是最大值和次大值，你的表达式变一会失败的。最值应该是 arr[arr.length-1]，面试的话这样写肯定挂的。我的问题再好好看看。

chslzj 发表于 2013-7-5 20:56
如果数组没有经过排序，那如果要找到最值，应该一定要遍历一遍吧，在遍历过程中找到最值应该是最快的 ...

我问的是最大值和次大值问题，不是单纯的最值。:handshake

如果数组没有经过排序，那如果要找到最值，应该一定要遍历一遍吧，在遍历过程中找到最值应该是最快的

Arrays.sort(arr);
int max = arr[arr.length]