如何在整数数组中找到第二高的数字？

Question

如何在整数数组中找到第二高的数字？

这是一个很好的实现吗？

有一个更好的方法吗？

public class Find2ndHighest {
    public static void main(String[] args) {
        int b[] = {2,3,1,0,5};

        TreeMap<Integer,Integer> tree = new TreeMap<Integer,Integer>();
        for(int i = 0; i<b.length;i++){
            tree.put(b[i], 0);
        }
        System.out.println(tree.floorKey(tree.lastKey()-1));
    }
}

Answer 1

您可以对数组进行排序并获取在O(nlogn)中执行的倒数第二个元素,但只有在您确定数组中没有重复项时才会起作用,否则此方法不可靠.

您可以遍历数组维护计数器以获得最高和第二高,并返回第二高.这在O(n)中执行

例:

 int highest = Integer.MIN_VALUE+1; 
 int sec_highest = Integer.MIN_VALUE;
 for(int i : b) //b is array of integers
 {
     if(i>highest)
     {
        sec_highest = highest; //make current highest to second highest
        highest = i; //make current value to highest
     }
     else if(i>sec_highest && i != highest) 
     {
        sec_highest = i;
     }
 }

另一种解决方案是

int b[] = {1, 2, 31,22,12,12};
Arrays.sort(b);
System.out.println(b[b.length-2]);