如何找到整数数组中第二大的数?
这是一个好的实现吗?
有更好的方法吗?
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));
}
}
您可以对数组进行排序并获取在 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]);