如何按降序打印二维数组的值？

Question

我有一个二维矩阵，想要按从大到小的顺序打印出其中的值。我会通过查找最大值，并将其位置设置为adjacencyMatrix中的1来实现这个目标，以便我们不再计算它。问题是，当我测试代码时，它开始正确地打印出最大值，然后跳过了第二大的值。接着找到了第三和第四大的值。又跳过了一些值，最后只打印出0。

以下是我的代码：

public static void findLongestPath(int rows, int columns, int[][] elevationMatrix, int[][] adjacencyMatrix)
    {
        int max = 0;

        for (int x = 0; x < rows * columns; x++)
        {   
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    if (elevationMatrix[i][j] > max && adjacencyMatrix[i][j] == 0)
                    {
                        max = elevationMatrix[i][j];
                        adjacencyMatrix[i][j] = 1;
                    }
                }
            }

            System.out.println(max);
            max = 0;
        }
    }

我已经盯着它看了一段时间，但找不到错误，所以我认为再请另外一双眼睛来帮忙。

附言：拜托、拜托、拜托别让我对数组进行排序，因为我无法这样做。我需要保持原始数组的顺序。

- Isabel Alphonse

---

制作一个大小为 rows * columns 的一维副本，并对其进行排序。 - Louis Wasserman

@LouisWasserman 我会失去位置。这是一个大程序的一部分，我需要知道每个值的位置。 - Isabel Alphonse

然后，您将编写一个实现Comparable接口的类，存储位置和值，然后对它们进行排序。 - Louis Wasserman

不确定您的意思。另外，我这样做有什么问题吗？ - Isabel Alphonse

首先，它将需要 行数 * 列数 * 行数 * 列数 步骤，这将是永远的。 - Louis Wasserman

确切地说，如果您使用对象并对其进行排序，则需要O(nLogn)的时间，其中n=行+列，这比O(row^2*columns^2)要低得多。 - Ahmed Amr

Answer 1

public static void findLongestPath(int rows, int columns, int[][] elevationMatrix, int[][] adjacencyMatrix)
    {
        int max = 0;
        int cX, cY;

        for (int x = 0; x < rows * columns; x++)
        {   
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < columns; j++)
                {
                    if (elevationMatrix[i][j] > max && adjacencyMatrix[i][j] == 0)
                    {
                        max = elevationMatrix[i][j]; // possible max, xth iteration
                        cX = i; // store i
                        cY = j; // store j
                    }
                }
            }

            System.out.println(max); // global max, xth iteration
            max = 0;
            // cX and cJ now point to coordinates of global max
            // all the possible max value coordinates are ignored.
            adjacencyMatrix[cX][cJ] = 1;
        }
    }

我认为你需要在找到矩阵中的最大数（全局最大值）后，设置adjacencyMatrix[][] = 1，而不是找到一个可能的最大值。

可能有更高效的方法来完成这个任务，我只是指出了这个方法需要做什么才能工作。

- Ankit Deshpande

---

我已经添加了注释，请参考它们。如果还不清楚，请留言。很乐意帮助 :-) - Ankit Deshpande

Answer 2

public static void findLongestPath(int rows, int columns, int[][] elevationMatrix)
{
   class PosAndValue implements Comparable<PosAndValue> {
     final int x;
     final int y;
     final int value;
     PosAndValue(int x, int y, int value) {
       this.x = x;
       this.y = y;
       this.value = value;
     }
     public int compareTo(PosAndValue other) {
       return Integer.compare(value, other.value);
     }
   }
   PosAndValue[] array = new PosAndValue[rows * columns];
   for (int i = 0; i < rows; i++) {
     for (int j = 0; j < columns; j++) {
       array[i * columns + j] = new PosAndValue(i, j, elevationMatrix[i][j]);
     }
   }
   Arrays.sort(array);
   for (int i = array.length - 1; i >= 0; i--) {
     System.out.println(array[i].value);
   }
}

- Louis Wasserman

Answer 3

问题在于你正试图伪排序。

只需制作所有值的列表或1D数组并对其进行排序即可。如果您在方法中声明了临时数组，则垃圾收集线程最终会将其拾取。

你的方法可能有 ~10 行：将所有值添加到临时数组中，对其进行排序，打印所有值。

int[] tempArr = new int[rows * columns];
for(int i = 0; i < rows; i++){
    for(int j = 0; j < columns; j++){
        tempArr[(i * col) + j] = elevationMatrix[i][j];
    }
}
Arrays.sort(tempArr);
for(int x = (rows * columns) - 1; x >= 0; x--){
    System.out.println(tempArr[x]);
}

- JMekker

---

OP已经说过他们需要追踪原始位置。 - Louis Wasserman

他说他需要保持原始数组的顺序。这样做就可以了。 - JMekker

但是它并没有告诉你，当你遍历 tempArr[x] 时，这个值最初来自于 elevationMatrix 的哪个位置，而且 OP 在评论中已经说了他们需要这个信息。 - Louis Wasserman

好的。我没有看到那个。不过把它加入到这里并不难，但我看到楼主已经找到了答案。 - JMekker