如何在二维数组中找到前 5 个最大值？

Question

我有一个二维整数数组。行和列信息（数字的位置）对我很重要。所以，我不想对数组（实际上是矩阵）进行排序。如何从这个二维数组中找到最高的 5 个值？

这是我的代码：

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

Answer 1

让MAX_N = 5.
求count作为matrix[][]中的元素总数。
创建 flattened = new int[count] 并用 matrix[][] 的所有元素填充它。
创建 max = new int[MAX_N] 来存储最大 n 个数字。另外，创建 maxPos = new int[MAX_N] 来存储最大数字的位置。
循环 MAX_N 次，在每次迭代中，假设 flattened[0] 是最大的数字。
如果flattened[j] >= max[i]，检查位置j是否已经被处理。如果不分配 flattened[j] 到 max[i] 和 j 到 maxPos[i].

演示：

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        final int MAX_N = 5;
        int[][] matrix = {
                {16, -20, 11, 19},
                {2, 5, 6, 8},
                {17, 25, 16, 19},
                {7, 17, 4, 17}};

        // 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;
                    }
                }
            }
        }
        System.out.println("Largest " + MAX_N +
                " values: " + Arrays.toString(max));
    }
}

输出：

Largest 5 values: [25, 19, 19, 17, 17]

Answer 2

如果不对数组本身进行排序，您可以在该数组上创建 sorted 流。或者你可以实现一种选择排序降序。这两个代码示例做同样的事情 - 在二维数组中找到前 5 个最高的 distinct 值，如果它们存在：

int[][] arr = {
        {1, 4, 7, 7},
        {2, 5, 8, 3},
        {5, 5, 1, 2},
        {3, 6, 0, 9}};

int[] max = Arrays.stream(arr)
        .flatMapToInt(Arrays::stream)
        .boxed().sorted(Comparator.reverseOrder())
        .mapToInt(Integer::intValue)
        .distinct()
        .limit(5)
        .toArray();

System.out.println(Arrays.toString(max)); // [9, 8, 7, 6, 5]

int[][] arr = {
        {1, 4, 7, 7},
        {2, 5, 8, 3},
        {5, 5, 1, 2},
        {3, 6, 0, 9}};

int[] max = new int[5];

for (int m = 0; m < max.length; m++) {
    int prev_max = m > 0 ? max[m - 1] : Integer.MAX_VALUE;
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr[i].length; j++) {
            if (arr[i][j] > max[m] && prev_max > arr[i][j]) {
                max[m] = arr[i][j];
            }
        }
    }
}

System.out.println(Arrays.toString(max)); // [9, 8, 7, 6, 5]

^{另请参阅：Selection sort of array}

Answer 3

现在问题又开放了，我将发表我的评论作为答案。

我用 Integer.MIN_VALUE 填充 int[] highestNumbers，而不是多次遍历同一个矩阵，遍历矩阵一次，并在每次当前整数较大时替换 max 的最小条目，通过更新 highestNumbers 的第一个条目并对其进行排序。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[][] matrix = {
                {10, -5, 15},
                {8, 20, 12},
                {27, -3, 14},
                {7, 17, 4}};
        int[] highestNumbers = new int[5];
        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);
                }
            }
        }
        System.out.println(Arrays.toString(highestNumbers));
    }
}

输出：

[14, 15, 17, 20, 27]

Answer 4

使用 Java8 流可以用这（一行）代码来完成。它将使原始矩阵保持不变。

Arrays.stream(matrix) // create a stream of the matrix
      .flatMapToInt(Arrays::stream) //Reduce 2d matrix to 1d 
      .boxed() //Convert int to Integer so we can sort reversed order
      .sorted(Collections.reverseOrder()) //sort array in reversed order highest first
      .limit(5) //Limit stream to 5 entries, the five top results
      .forEach(System.out::println); //Print the result

Answer 5

您可以使用以下方式，这会给您带来以下好处：

保持非常简单的逻辑，因为你想要最高的 5 个值并且你不会丢失现有数组的任何索引 location/order，
使用这个你会得到更好的性能，
清洁代码。

public static void main(String[] args) {
    int[][] matrix = {
            {10, -5, 15},
            {8, 20, 12},
            {27, -3, 14},
            {7, 17, 4}};

    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(5)
            .collect(Collectors.toList());

    System.out.println(allVal);
}

输出：

[27, 20, 17, 15, 14]

Answer 6

首先，我寻求与其他答案非常相似的流解决方案。我不喜欢装箱和拆箱的变体，但由于 IntStream 没有一种奇特的方法可以直接使用 Comparator 进行排序，所以 IntStream 必须是转换为 Stream 以便按相反顺序对值进行排序。我认为 return 一个 int[] 数组并不重要，因为我们只真正对值感兴趣。

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[] 数组中，请查看使用 mapToInt() 的 by shadow.sabre。

虽然流解决方案看起来非常整洁，但我觉得问题实际上只是获取最高值的集合，因此将它们插入标准 java 排序 Set对我来说有意义。我首先将值插入到集合中，直到其中有 5 个元素。然后我检查新值是否高于最低值，如果是，我只删除最低值，同时插入新值。使用 TreeSet 时很容易找到最低值，因为它是一个排序集。

诀窍是还要检查集合中是否还没有新值。如果集合中已经有 5、4、3、2、1，并且新值是 5，那么我不想删除最低值 1，因为添加新值实际上不会添加任何新元素集。请记住 Set 不能包含重复值：

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

请注意，此解决方案显然从不包含相同的值，但始终包含最重要的不同值。

查看集合解决方案，很容易添加附加功能来跟踪在矩阵中找到值的位置。我创建了一个 class、Element 来包含值及其位置。矩阵中要插入 TreeSet 的每个元素都创建为 Element.

Element 需要 implement Comparable 或 TreeSet 必须用 Comparator 初始化以便对元素进行排序。这个Element的例子两者都有，我只是在compareTo(Element that)的实现中使用了static Comparator使其成为Comparable<Element>。通常，您会使用 getter 来实现带有私有字段的 class 来获取值，但为此目的似乎有点冗长。使字段 final 还确保 class 是不可变的，所以我对此毫无顾忌。

由于比较是使用值和位置完成的，因此矩阵中的每个元素都是不同的：

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:

的初始化

TreeSet<Element> maxElement = new TreeSet<>(Element.comparator);

但是由于 Element 确实实现了 Comparable 接口，所以可以在没有它的情况下初始化集合实现：

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

请注意，因为每个元素都是不同的，所以没有必要同时检查集合中是否还没有新值。

运行给定输入的三个解：

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]]

但是性能呢？

这三种不同的实现让我想知道性能，所以我添加了一个方法来计时执行：

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 的解决方案似乎会造成损失。但是为了更深入地研究它，我决定运行它们在一个更大的矩阵上，我使用运行dom 整数构建它：

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 矩阵的测试：

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

..给出了这个结果：

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 解决方案是在每次比较值时拆箱。不过我没有进一步检验我的假设。

我对这个线程中其他解决方案的好奇心促使我也测试了这些解决方案。测试的解决方案是：

运行小数组和大数组的测试：

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

..给出了这些结果：

--- 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 的解决方案是迄今为止性能更好的解决方案。

全部代码

如果你想自己运行，这里有一个完整的class用于复制'n'粘贴'n'运行:

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?"]( by [Arvind Kumar Avinash](https://whosebug.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?"]( by [Anurag Jain](https://whosebug.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?"]( by [Michael Chatiskatzi](https://whosebug.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 + "]";
  }
}