黑马程序员技术交流社区

标题: 关于取得整型无序数组中第二大的元素 [打印本页]
作者: 爱翚    时间: 2014-4-23 08:06
标题: 关于取得整型无序数组中第二大的元素
本帖最后由 爱翚 于 2014-4-23 15:12 编辑

昨天我的一个朋友向我请教一个面试题.题目的名字是从一个无序的整型数组中快速的查找出第二大的元素,要充分考虑空间复杂度和时间复杂度.

下面是我写的一段代码,思路是先排序在从排序后的结果中取出第二个元素.
我想请教一下有没有更好的写法?最好是不用排序的.

public static void main(String[] args){
      int arr[] = {4, 3, 5, 9, 6, 8, 9, 2, 1, 7};
      int temp;     
      int i, j;     
      for (i=0; i<9; i++) {
           for (j=i+1; j<10; j++) {            
        if (arr > arr[j]) {                 
            temp = arr;                 
            arr = arr[j];                 
            arr[j] = temp;            
                }         
            }     
        }
       System.out.println("数组中第二大的元素为:"+arr[1]);
}
作者: kuroro自走核炮    时间: 2014-4-23 08:42
  1. class Demo4
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int arr[] = {4,3,5,9,6,8,9,2,1,7,11,15,18,15,16,19};
  6.                 int temp;
  7.                 int x,y;
  8.                 if(arr[0]>arr[1])
  9.                 {
  10.                         x=arr[0];
  11.                         y=arr[1];
  12.                 }
  13.                 else
  14.                 {
  15.                         x=arr[1];
  16.                         y=arr[0];
  17.                
  18.                 }
  19.                 for (int i=2; i<arr.length/*数组长度,保证角标索引i的值不会越界。*/; i++)
  20.                 {
  21.                         if(arr[i]>y)//arr[i]>y>x
  22.                         {
  23.                                 x=y;
  24.                                 y=arr[i];               
  25.                         }
  26.                         else if(arr[i]<y&&arr[i]>x)//y>arr[i]>x
  27.                         {
  28.                                 x=arr[i];                                               
  29.                         }
  30.                         else//arr[i]=y,arr[i]=x,y>x>arr[i]这些情况
  31.                         {
  32.                         }

  34.                 }
  35.                 System.out.println("数组中第二大的元素为:"+x);
  36.         }
  37. }
复制代码

这样遍历一遍就出结果了，而且可以排除相同值元素影响，效率应该比你那个要高点。
作者: 爱翚    时间: 2014-4-23 10:09
kuroro自走核炮 发表于 2014-4-23 08:42
这样遍历一遍就出结果了，而且可以排除相同值元素影响，效率应该比你那个要高点。 ...

谢谢您的回答.
作者: 今生无憾    时间: 2014-4-23 10:20
本帖最后由 今生无憾 于 2014-4-23 10:22 编辑

其实只要简单的把你的思路改一下即可 ，选择排序，原理就是每轮选出剩余元素中的最大值，也就是第二轮就能得到你想要的值。把你代码的第一层循环，i<9改成小于2就好了。 简单易懂。至于复杂度-显而易见;。  




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