黑马程序员技术交流社区

标题: 怎么从数组中很快的获得最大值和次大值呢？ [打印本页]

作者: 宋旭东 时间: 2013-7-5 20:10
标题: 怎么从数组中很快的获得最大值和次大值呢？
从数组中获得最大值和次大值，这是个公司的面试题目，本人开始觉得排个序就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]

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

作者: 宋旭东 时间: 2013-7-5 22:39

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

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

作者: 宋旭东 时间: 2013-7-5 22:41

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

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

作者: hanrongle 时间: 2013-7-5 23:04
可以用递归算法，就是把数组二等分，找出每一段的最大值，就这样逐次递归。最后会有两个最大值，这两个值肯定是最大值和次大值。

作者: longlangcx 时间: 2013-7-5 23:41
本帖最后由 longlangcx 于 2013-7-6 09:11 编辑

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

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

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

或者这样：

class MaxSec
{
public static void main(String[] args)
{
int[] arr = new int[]{100,3,2,5,23,6,7,34,5,25,8,1000};
int max = arr[0], sec = Integer.MIN_VALUE;
for(int i = 1; i < arr.length; i++){
if (sec <= arr[i])
{
if (max <= arr[i])
{
sec = max;
max = arr[i];
}
else
sec = arr[i];
}
}
System.out.println(max + ", " + sec);
}
}

复制代码

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

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

作者: 王靖远 时间: 2013-7-6 09:11

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

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

作者: 王靖远 时间: 2013-7-6 10:17

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

嘿嘿没注意。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2