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

html5 • • 问答

我有一个二维整数数组。行和列信息（数字的位置）对我很重要。所以，我不想对数组（实际上是矩阵）进行排序。如何从这个二维数组中找到最高的 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];
    }
  }
}

回答

首先，我选择了一个与其他答案非常相似的流解决方案。我不喜欢装箱和拆箱的变化，但由于IntStream没有一种花哨的方法可以Comparator直接开箱即用进行排序，因此IntStream必须将其转换为 aStream以便以相反的顺序对值进行排序。我认为返回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[]数组中，请查看使用do的shadow.sabre的答案。mapToInt()

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

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

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

请注意，此解决方案显然永远不会包含相同的值，但始终是最上面不同的值。

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

The Elementneed to implement Comparableor theTreeSet必须用 a 初始化，Comparator以便对元素进行排序。这个例子Element有两者，我只是static Comparator在实现中使用了，compareTo(Element that)使它成为一个Comparable<Element>. 通常，您会使用 getter 来实现具有私有字段的类来获取值，但为此目的似乎有点冗长。制作字段final还可以确保该类是不可变的，因此我对此毫无顾忌。

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

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接口，因此可以在没有它的情况下初始化 set 实现：

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

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

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

使用 10000 x 10000 矩阵运行测试：

..给了这个结果：

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

这里的流解决方案似乎非常慢！该Element解决方案是两个冠军Set的解决方案。我希望这是因为Elements 仅在需要插入时才创建，Set并且它正在进行直接int比较，而另一个Set解决方案是每次比较值时拆箱。不过，我没有进一步检验我的假设。

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

  • 答案由阿尔温德·库马尔阿维纳什
  • 答案由阿努拉格耆那教
  • 答案由迈克尔Chatiskatzi

在小型和大型阵列上运行测试：

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

似乎使用流的解决方案根本不是很高效。Michael Chatiskatzi的解决方案是迄今为止性能更好的解决方案。

所有的代码

如果你想自己运行它，这里有一个完整的 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?"](/sf/answers/4576246531/) by [Arvind Kumar Avinash](/sf/users/757370141/)

    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?"](/sf/answers/4576637901/) by [Anurag Jain](/sf/users/407793781/)

    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?"](/sf/answers/4576594501/) by [Michael Chatiskatzi](/sf/users/788432431/)

    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.o
以上是如何在二维数组中找到前5个最高值？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>