如何在二维数组中找到前 5 个最高值? [英] How to find first 5 highest value in a two dimensional array?
问题描述
我有一个二维整数数组.行和列信息(数字的位置)对我很重要.所以，我不想对数组(实际上是矩阵)进行排序.如何从这个二维数组中找到最高的 5 个值?
I have a two dimensional integer array. Row and Column information (locations of numbers) is important for me. So, I don't want to sort an array (matrix actually). How can I find the highest 5 value from this two dimensional array?
这是我的代码:
for (int row = 0; row < matirx.length; row++) {
for (int col = 0; col < matirx[row].length; col++) {
if (matirx[row][col] > maxValue) {
maxValue = matirx[row][col];
}
}
}
推荐答案
首先，我选择了一个与其他 Answers 非常相似的流解决方案.我不喜欢装箱和拆箱的变化，但是由于 IntStream 没有一种花哨的方法可以直接使用 Comparator 进行排序，IntStream 必须转换为 Stream 以便以相反的顺序对值进行排序.我认为返回 int[] 数组并不重要，因为我们只对值感兴趣.
First, I went for a streams solution that is very similar to other Answers. I didn't like the boxing and unboxing variations, but since IntStream doesn't have a fancy method that makes sorting with a Comparator straight out of the box, the IntStream has to be converted into a Stream in order to sort the values in reverse order. I didn't think it was important to return an int[] array, since we're only really interested in the values.
public static Integer[] streamIt(int[][] matrix, int n){
Integer[] result =
Arrays.stream(matrix) // stream the arrays
// This is the same as using .flatMaptoInt(..) and then .boxed()
.flatMap(a -> Arrays.stream(a) // stream the array in arrays
.mapToObj(i -> Integer.valueOf(i))) // turn the ints into Integers
.sorted(Comparator.reverseOrder()) // sort by higest values
.limit(n) // only pick n
.toArray(i -> new Integer[i]); // put then in Integer array
return result;
}
如果您希望将它们放在 int[] 数组中，请查看 答案通过 shadow.sabre 使用 mapToInt() 做到这一点.
If you want them in an int[] array instead, look at the Answer by shadow.sabre that uses mapToInt() do to that.
虽然流解决方案看起来非常整洁干净，但我觉得问题真的只是为了获得最高值的集合，所以将它们插入到标准的 java 排序 Set 中对我来说很有意义.我首先将值插入到集合中，直到那里有 5 个元素.然后我检查新值是否高于最低值，如果是，我只是在插入新值时删除最低值.使用 TreeSet 时很容易找到最小值，因为它是一个排序集.
While the streams solution is very neat and clean looking, I felt that the problem was really just to get the set of highest values, so inserting them into a standard java sorted Set made sense to me. I start off by inserting the values into the set until there are 5 elements in there. Then I check to see if the new value is higher than the lowest value, and if so, I just remove the lowest value while inserting the new one. Finding the lowest value is easy when using TreeSet as it's a sorted set.
诀窍是还要检查新值是否已经在集合中.如果集合中已经有 5、4、3、2、1，并且新值是 5，那么我不想删除最低值 1，因为添加新值实际上不会向其中添加任何新元素集.记住 Set 不能包含重复值:
The trick is to also check that the new value isn't already in the set. If there's already 5, 4, 3, 2, 1 in the set, and the new value is 5, then I don't want to remove the lowest value 1, since adding the new value wouldn't actually add any new elements to the Set. Remember a Set cannot contain duplicate values:
public static Set<Integer> useSet(int[][] matrix, int n){
TreeSet<Integer> max = new TreeSet<>(Comparator.<Integer>naturalOrder().reversed());
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
// Keep adding values until there's n elements in the Set
if (max.size() < n) {
max.add(matrix[i][j]);
} else {
// if the new value is higher than the lowest value
// ..and the new values isn't already there.
if (max.last() < matrix[i][j] && !max.contains(matrix[i][j])) {
max.pollLast();
max.add(matrix[i][j]);
}
}
}
}
return max;
}
请注意，此解决方案显然从不包含相同的值，但始终包含最上面不同的值.
Note that this solution obviously never contains the same values, but always the top distinct ones.
查看设置的解决方案，很容易添加跟踪矩阵中找到值的位置的附加功能.我创建了一个类 Element 来包含值及其位置.矩阵中要插入 TreeSet 的每个元素都创建为 Element.
Looking at the set solution it was easy to add the additional functionality of keeping track of where in the matrix the values were found. I created a class, Element, to contain the value and its location. Every element in the matrix that's to be inserted into the TreeSet is created as an Element.
Element 需要 implement Comparable 或者 TreeSet 必须用 Comparator 初始化对元素进行排序.这个 Element 的例子两者都有，我只是在 compareTo(Element that) 的实现中使用了 static Comparator 使它成为一个 可比较的<元素>.通常，您会使用 getter 来实现具有私有字段的类来获取值，但为此目的似乎有点冗长.将字段设为 final 还可以确保该类是不可变的，因此我对此毫无顾忌.
The Element needs to either implement Comparable or the TreeSet has to be initialized with a Comparator in order to sort the elements. This example of Element has both, and I just used the static Comparator in the implementation of compareTo(Element that) to make it a Comparable<Element>. Normally you'd implement the class with private fields using getters to fetch the values, but for this purpose is seemed a little verbose. Making the fields final also ensures the class is immutable so I have no scruples about it.
因为比较是使用值和位置完成的，矩阵中的每个元素都是不同的:
Since the comparison is done using both the value and the location, every element from the matrix will be distinct:
class Element implements Comparable<Element> {
final int value;
final int x;
final int y;
static Comparator<Element> comparator =
Comparator.comparing((Element e) -> e.value)
.thenComparing((Element e) -> e.x)
.thenComparing((Element e) -> e.y)
.reversed();
Element(int value, int x, int y) {
this.value = value;
this.x = x;
this.y = y;
}
public int compareTo(Element that){
return comparator.compare(this, that);
}
public String toString(){
return value + " at [" + x + "][" + y + "]";
}
}
如果 Element 没有实现 Comparable 接口，这将是 TreeSet 的初始化:
If the Element didn't implement the Comparable interface, this would be the initialization of the TreeSet:
TreeSet<元素>maxElement = new TreeSet<>(Element.comparator);
但是由于 Element 确实实现了 Comparable 接口，所以可以在没有它的情况下初始化 set 实现:
But since Element does implement the Comparable interface, the set implementation can be initialized without it:
public static Set<Element> useSetElements(int[][] matrix, int n){
TreeSet<Element> maxElement = new TreeSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (maxElement.size() < n) {
maxElement.add(new Element(matrix[i][j],i,j));
} else {
if (maxElement.last().value < matrix[i][j]) {
maxElement.pollLast();
maxElement.add(new Element(matrix[i][j],i,j));
}
}
}
}
return maxElement;
}
请注意，由于每个元素都是不同的，因此无需检查新值是否已存在于集合中.
Note that because every element is distinct, there's no need to also check that the new value isn't already in the set.
使用给定的输入运行三个解决方案:
Running the three solutions with given input:
int n = 5;
int[][] matrix = {{16, -20, 22, 19},
{ 2, 5, 6, 8},
{17, 25, 16, 19},
{ 7, 18, 4, 17}};
System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(matrix,n)));
System.out.println("useSet: \n "
+ useSet(matrix,n));
System.out.println("useSetElements: \n "
+ useSetElements(matrix,n));
...给出:
streamIt:
[25, 22, 19, 19, 18]
useSet:
[25, 22, 19, 18, 17]
useSetElements:
[25 at [2][1], 22 at [0][2], 19 at [2][3], 19 at [0][3], 18 at [3][1]]
但是性能呢...?
这三种不同的实现让我对性能感到疑惑，所以我添加了一个方法来计时:
But what about Performance..?
The three different implementations had me wondering about the performance, so I added a method to time the execution:
static void timeMethod(Runnable toRun){
long start = System.nanoTime();
try{
toRun.run();
} finally {
long end = System.nanoTime();
System.out.println(" Time: " + (end - start)/1.0e6 + " miliseconds");
}
}
并运行三个解决方案:
timeMethod(() -> System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(matrix,n))));
timeMethod(() -> System.out.println("useSet: \n "
+ useSet(matrix,n)));
timeMethod(() -> System.out.println("useSetElements: \n "
+ useSetElements(matrix,n)));
...给出这个结果:
streamIt:
[25, 22, 19, 19, 18]
Time: 1.2759 miliseconds
useSet:
[25, 22, 19, 18, 17]
Time: 0.9343 miliseconds
useSetElements:
[25 at [2][1], 22 at [0][2], 19 at [2][3], 19 at [0][3], 18 at [3][1]]
Time: 1.16 miliseconds
似乎这三种解决方案的性能大致相同.流解决方案似乎稍慢.Set 解决方案看起来很有希望，但使用 Element 的解决方案似乎要付出代价.但是为了更深入地研究它，我决定在一个更大的矩阵上运行它们，我使用随机整数构建:
It seems that the three solutions have roughly the same performance. The streams solution seems slightly slower. The Set solution looks promising, expect the solution using Element seems to take a toll. But to look at it more deeply I decided to run them on a much larger matrix, which I build using random integers:
Random random = new Random();
int[][] largerMatrix =
IntStream.range(0,10000) // 10000 on the first dimension
.mapToObj(i -> random.ints(0,128) // values between 0 and 128 (not included)
.limit(10000) // 10000 on the second dimension
.toArray()) // make the second 1D arrays
.toArray(int[][]::new); // put them into a 2D array
使用 10000 x 10000 矩阵运行测试:
Running the test with a 10000 by 10000 matrix:
timeMethod(() -> System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(largerMatrix,n))));
timeMethod(() -> System.out.println("useSet: \n "
+ useSet(largerMatrix,n)));
timeMethod(() -> System.out.println("useSetElements: \n "
+ useSetElements(largerMatrix,n)));
...给出了这个结果:
..gave this result:
streamIt:
[127, 127, 127, 127, 127]
Time: 90374.6995 miliseconds
useSet:
[127, 126, 125, 124, 123]
Time: 2465.2448 miliseconds
useSetElements:
[127 at [0][310], 127 at [0][277], 127 at [0][260], 127 at [0][81], 127 at [0][61]]
Time: 1839.7323 miliseconds
这里的流解决方案似乎非常慢！Element 解决方案是两个 Set 解决方案的赢家.我期望这是因为 Element 仅在需要插入 Set 时才创建，并且它是直接执行的int 比较，而另一个 Set 解决方案在每次比较值时都进行拆箱.不过我没有进一步检验我的假设.
Here the streams solution seems incredibly slow! The Element solution is the winner of the two Set solutions. I expect it's due to the fact that Elements are only created when they're needed for inserting into the Set and it's doing a straight up int comparison, while the other Set solution is unboxing every time the values are compared. I didn't further test my hypothesis though.
我对本主题中其他解决方案的好奇心让我也测试了这些解决方案.测试的解决方案是:
My curiosity of the other solutions in this thread got me testing out those as well. The solutions tested were:
在小型和大型阵列上运行测试:
Running the tests on both the small and the large array:
System.out.println("--- Testing performance ---");
timeMethod(() -> System.out.println("ArvindKumarAvinash: \n "
+ Arrays.toString(ArvindKumarAvinash(matrix,n))));
timeMethod(() -> System.out.println("AnuragJain: \n "
+ AnuragJain(matrix,n)));
timeMethod(() -> System.out.println("MichaelChatiskatzi: \n "
+ Arrays.toString(MichaelChatiskatzi(matrix,n))));
System.out.println();
System.out.println("--- Testing performance with largeMatrix---");
timeMethod(() -> System.out.println("ArvindKumarAvinash: \n "
+ Arrays.toString(ArvindKumarAvinash(largerMatrix,n))));
timeMethod(() -> System.out.println("AnuragJain: \n "
+ AnuragJain(largerMatrix,n)));
timeMethod(() -> System.out.println("MichaelChatiskatzi: \n "
+ Arrays.toString(MichaelChatiskatzi(largerMatrix,n))));
...给出了这些结果:
..gave these results:
--- Testing performance ---
ArvindKumarAvinash:
[25, 22, 19, 19, 18]
Time: 0.9076 miliseconds
AnuragJain:
[25, 22, 19, 19, 18]
Time: 6.2277 miliseconds
MichaelChatiskatzi:
[18, 19, 19, 22, 25]
Time: 1.2204 miliseconds
--- Testing performance with largeMatrix---
ArvindKumarAvinash:
[127, 127, 127, 127, 127]
Time: 3381.1387 miliseconds
AnuragJain:
[127, 127, 127, 127, 127]
Time: 120244.7063 miliseconds
MichaelChatiskatzi:
[127, 127, 127, 127, 127]
Time: 51.4259 miliseconds
似乎使用流的解决方案的性能根本不高.Michael Chatiskatzi 的解决方案是迄今为止性能更好的解决方案.
It seems that solutions using streams are not very performant at all. Michael Chatiskatzi's solution is by far the better performant one.
如果你想自己运行它，这里有一个完整的复制'n'paste'n'run类:
If you want to run it yourself, here a complete class for copy'n'paste'n'run:
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;
import java.util.Set;
import java.util.TreeSet;
import java.util.Comparator;
import java.util.Random;
import java.util.List;
import java.util.ArrayList;
import java.util.stream.Collectors;
public class GettingTheTopN {
public static void main(String[] args) {
int n = 5;
int[][] matrix = {{16, -20, 22, 19},
{ 2, 5, 6, 8},
{17, 25, 16, 19},
{ 7, 18, 4, 17}};
System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(matrix,n)));
System.out.println("useSet: \n "
+ useSet(matrix,n));
System.out.println("useSetElements: \n "
+ useSetElements(matrix,n));
System.out.println();
System.out.println("--- Testing performance ---");
timeMethod(() -> System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(matrix,n))));
timeMethod(() -> System.out.println("useSet: \n "
+ useSet(matrix,n)));
timeMethod(() -> System.out.println("useSetElements: \n "
+ useSetElements(matrix,n)));
timeMethod(() -> System.out.println("ArvindKumarAvinash: \n "
+ Arrays.toString(ArvindKumarAvinash(matrix,n))));
timeMethod(() -> System.out.println("AnuragJain: \n "
+ AnuragJain(matrix,n)));
timeMethod(() -> System.out.println("MichaelChatiskatzi: \n "
+ Arrays.toString(MichaelChatiskatzi(matrix,n))));
System.out.println();
System.out.println("--- Testing performance with largeMatrix---");
Random random = new Random();
int[][] largerMatrix =
IntStream.range(0,10000) // 10000 on the first dimension
.mapToObj(i -> random.ints(0,128) // values between 0 and 128 (not included)
.limit(10000) // 10000 on the second dimension
.toArray()) // make the second 1D arrays
.toArray(int[][]::new); // put them into a 2D array
timeMethod(() -> System.out.println("streamIt: \n "
+ Arrays.toString(streamIt(largerMatrix,n))));
timeMethod(() -> System.out.println("useSet: \n "
+ useSet(largerMatrix,n)));
timeMethod(() -> System.out.println("useSetElements: \n "
+ useSetElements(largerMatrix,n)));
timeMethod(() -> System.out.println("ArvindKumarAvinash: \n "
+ Arrays.toString(ArvindKumarAvinash(largerMatrix,n))));
timeMethod(() -> System.out.println("AnuragJain: \n "
+ AnuragJain(largerMatrix,n)));
timeMethod(() -> System.out.println("MichaelChatiskatzi: \n "
+ Arrays.toString(MichaelChatiskatzi(largerMatrix,n))));
}
public static Integer[] streamIt(int[][] matrix, int n){
Integer[] result =
Arrays.stream(matrix) // stream the arrays
// This is the same as using .flatMaptoInt(..) and then .boxed()
.flatMap(a -> Arrays.stream(a) // stream the array in arrays
.mapToObj(i -> Integer.valueOf(i))) // turn the ints into Integers
.sorted(Comparator.reverseOrder()) // sort by higest values
.limit(n) // only pick n
.toArray(i -> new Integer[i]); // put then in Integer array
return result;
}
public static Set<Integer> useSet(int[][] matrix, int n){
TreeSet<Integer> max = new TreeSet<>(Comparator.<Integer>naturalOrder().reversed());
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
// Keep adding values until there's n elements in the Set
if (max.size() < n) {
max.add(matrix[i][j]);
} else {
// if the new value is higher than the lowest value
// ..and the new values isn't already there.
if (max.last() < matrix[i][j] && !max.contains(matrix[i][j])) {
max.pollLast();
max.add(matrix[i][j]);
}
}
}
}
return max;
}
public static Set<Element> useSetElements(int[][] matrix, int n){
TreeSet<Element> maxElement = new TreeSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (maxElement.size() < n) {
maxElement.add(new Element(matrix[i][j],i,j));
} else {
if (maxElement.last().value < matrix[i][j]) {
maxElement.pollLast();
maxElement.add(new Element(matrix[i][j],i,j));
}
}
}
}
return maxElement;
}
// ----------------- Performance
static void timeMethod(Runnable toRun){
long start = System.nanoTime();
try{
toRun.run();
} finally {
long end = System.nanoTime();
System.out.println(" Time: " + (end - start)/1.0e6 + " miliseconds");
}
}
// [Answer to "How to find first 5 highest value in a two dimensional array?"](https://stackoverflow.com/a/65374950/12695027) by [Arvind Kumar Avinash](https://stackoverflow.com/users/10819573/arvind-kumar-avinash)
static int[] ArvindKumarAvinash(int[][] matrix, int MAX_N) {
// Find count as the total number of elements
int count = 0, row, col;
for (row = 0; row < matrix.length; row++) {
count += matrix[row].length;
}
// Create flattened = new int[count] and fill it with all elements of matrix[][]
int[] flattened = new int[count];
int i = 0;
for (row = 0; row < matrix.length; row++) {
for (col = 0; col < matrix[row].length; col++) {
flattened[i++] = matrix[row][col];
}
}
// Create max = new int[MAX_N] to store maximum n numbers.
// Also, create maxPos = new int[MAX_N] to store the position of the maximum numbers.
int[] max = new int[MAX_N];
int[] maxPos = new int[MAX_N];
// Loop MAX_N times. In each iteration, assume flattened[0] is the largest number.
for (i = 0; i < max.length; i++) {
max[i] = flattened[0];
for (int j = 1; j < flattened.length; j++) {
// If flattened[j] >= max[i], check if the position, j has already been
// processed. If not assign flattened[j] to max[i] and j to maxPos[i].
if (flattened[j] >= max[i]) {
boolean posAlreadyProcessed = false;
for (int k = 0; k <= i; k++) {
if (maxPos[k] == j) {
posAlreadyProcessed = true;
break;
}
}
if (!posAlreadyProcessed) {
max[i] = flattened[j];
maxPos[i] = j;
}
}
}
}
return max;
// System.out.println("Largest " + MAX_N + " values: " + Arrays.toString(max));
}
// [Answer to "How to find first 5 highest value in a two dimensional array?"](https://stackoverflow.com/a/65380541/12695027) by [Anurag Jain](https://stackoverflow.com/users/5825625/anurag-jain)
static List<Integer> AnuragJain(int[][] matrix, int n) {
List<Integer> allVal = new ArrayList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
allVal.add(matrix[i][j]);
}
}
allVal = allVal.stream()
.sorted(Comparator.reverseOrder())
.limit(n).collect(Collectors.toList());
return allVal;
// System.out.println(allVal);
}
// [Answer to "How to find first 5 highest value in a two dimensional array?"](https://stackoverflow.com/a/65379921/12695027) by [Michael Chatiskatzi](https://stackoverflow.com/users/11263320/michael-chatiskatzi)
static int[] MichaelChatiskatzi(int[][] matrix, int n) {
// int[] highestNumbers = new int[5];
int[] highestNumbers = new int[n];
Arrays.fill(highestNumbers, Integer.MIN_VALUE);
for (int row = 0; row < matrix.length; row++) {
for (int column = 0; column < matrix[row].length; column++) {
int currentEntry = matrix[row][column];
if (currentEntry > highestNumbers[0]) {
highestNumbers[0] = currentEntry;
Arrays.sort(highestNumbers);
}
}
}
return highestNumbers;
// System.out.println(Arrays.toString(highestNumbers));
}
}
// -------------------------------------------
// -------------------------------------------
class Element implements Comparable<Element> {
final int value;
final int x;
final int y;
static Comparator<Element> comparator =
Comparator.comparing((Element e) -> e.value)
.thenComparing((Element e) -> e.x)
.thenComparing((Element e) -> e.y)
.reversed();
Element(int value, int x, int y) {
this.value = value;
this.x = x;
this.y = y;
}
public int compareTo(Element that){
return comparator.compare(this, that);
}
public String toString(){
return value + " at [" + x + "][" + y + "]";
}
}
这篇关于如何在二维数组中找到前 5 个最高值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
