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

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

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]);
}

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.                         }
    
33. 
    
34.                 }
    
35.                 System.out.println("数组中第二大的元素为:"+x);
    
36.         }
    
37. }

复制代码

这样遍历一遍就出结果了，而且可以排除相同值元素影响，效率应该比你那个要高点。

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

谢谢您的回答.

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