Java 你如何在整数数组中找到第二大数字？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21419508/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do you find second highest number in an integer array?
提问by user3246790
How do you find second highest number in an integer array?
你如何在整数数组中找到第二大数字？
Is this a good implementation?
这是一个很好的实现吗？
Is there a better way to do this?
有一个更好的方法吗？
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));
}
}
采纳答案by hemanth
You can sort the array and fetch second last element which executes in O(nlogn), but this works only if you are sure that there are no duplicates in the array else this method is unreliable.
您可以对数组进行排序并获取以 O(nlogn) 执行的倒数第二个元素，但这仅在您确定数组中没有重复项时才有效，否则此方法不可靠。
You can iterate through the array maintain counters for highest and second highest and return 2nd highest. This executes in O(n)
您可以遍历数组维护最高和第二高的计数器并返回第二高。这在 O(n) 中执行
Example:
例子：
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;
}
}
Another solution is:
另一种解决方案是：
int b[] = {1, 2, 31,22,12,12};
Arrays.sort(b);
System.out.println(b[b.length-2]);
回答by Tim Kuipers
The easiest solution would be:
最简单的解决方案是：
public static void main(String[] args) {
int b[] = {2,3,1,0,5};
int highest = Integer.MIN_VALUE;
int highest2nd = Integer.MIN_VALUE;
for(int i :b )
if (i>=highest) {
highest2nd = highest;
highest = i;
} else if (i>= highest2nd)
highest2nd = i;
System.out.println(highest2nd);
}
Then you walk through the list only once, which is the best you can do from a 'Big O' standpoint.
然后你只浏览一次列表，从“大 O”的角度来看，这是你能做的最好的事情。
PS: depending on whether you want the second highest unique value, or the value that is stricly lower than the highest value, you could choose to put i>highestin the if-statement, instead of i>=highest.
PS：根据您是想要第二高的唯一值，还是严格低于最高值的值，您可以选择放入i>highestif 语句，而不是i>=highest.
回答by pepo
There are multiple ways to find the second highest element in an unsorted array:
有多种方法可以在未排序的数组中找到第二高的元素：
You can sort the array and take the second last element - runs in
O(n log n).You can store the elements in a TreeSet instead of an array, which is what you are doing - runs in
O(n log n)as well.Suppose for a while you want to get the highest element - all you have to do is to iterate over the whole aray once, while keeping the maximum in a variable. This way you can achieve
O(n)performance.You can do the same thing for the second highest element, but instead of keeping the highest element, you will keep the two highest elements. This way you can easily achieve
O(n)performance.The only problem with the last solution is that it does not scale well with the increasng
k. There is however a linear time algorithm to find thek-th highest element in an unsorted array - runs inO(n)for anyk(http://en.wikipedia.org/wiki/Selection_algorithm)
您可以对数组进行排序并取倒数第二个元素 - 在
O(n log n).您可以将元素存储在 TreeSet 而不是数组中，这就是您正在做的 - 也可以运行
O(n log n)。假设有一段时间你想获得最高的元素 - 你所要做的就是迭代整个数组一次，同时将最大值保持在一个变量中。这样您就可以实现
O(n)性能。你可以对第二高的元素做同样的事情，但不是保留最高的元素，而是保留两个最高的元素。通过这种方式，您可以轻松实现
O(n)性能。最后一个解决方案的唯一问题是它不能随着 increasng 的增加而很好地扩展
k。然而，有一个线性时间算法可以k在未排序的数组中找到第-th 个最高元素 - 运行在O(n)任何k（http://en.wikipedia.org/wiki/Selection_algorithm）
