java - 检索放入 HashMap 中的数组

Question

下面的代码是我为一个问题编写的答案，该问题要求将 n x n 2D 矩阵旋转 90 度(顺时针)，而不创建新的 2D 数组。例如，

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

我尝试逐行执行此操作，但我必须处理的问题是如果索引对已经更改该怎么办。因此，如果我尝试将索引对 [1, 2] 分配给 [0, 1]，但 [0,1] 之前已经更改了。我想出的解决方案是使用HashMap，将索引对放入数组中作为键，将原始数字作为值。

这是我的代码

public void rotate(int[][] matrix) {
        int n = matrix.length;
        HashMap<int[], Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                if(map.containsKey(new int[]{n-j,i})){
                    matrix[i][j] = map.get(new int[]{n-j, i});
                }
                else{
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n-j][i]; 
                    map.put(new int[]{n-j,i}, temp);
                }
            }
        }  

    }

但是，结果表明

if(map.containsKey(new int[]{n-j,i})){
                    matrix[i][j] = map.get(new int[]{n-j, i});
                }

这行代码没有搜索我之前放入的数组。我知道我每次都会创建一个新数组，但是它如何使 containsKey 不知道数组是否包含相同的数字(相同的数组)？谁能帮助我理解为什么在这里使用数组来标记索引对在 HashMap 中不起作用？

Answer 1

您不需要Map来旋转矩阵。您只需要一个 temp 变量。

旋转 3x3:

1 2 3
4 5 6
7 8 9

temp = 1，复制周围的角值，然后将值保存到下一个角:

1 2 3   7 2 3   7 2 3   7 2 3   7 2 1
4 5 6 → 4 5 6 → 4 5 6 → 4 5 6 → 4 5 6
7 8 9   7 8 9   9 8 9   9 8 3   9 8 3

重复边界值，temp = 2:

7 2 1   7 4 1   7 4 1   7 4 1   7 4 1
4 5 6 → 4 5 6 → 8 5 6 → 8 5 6 → 8 5 2
9 8 3   9 8 3   9 8 3   9 6 3   9 6 3

就地旋转就完成了，临时存储中只有 1 个值，即 O(1) 内存占用。

现在我将让您针对任何大小的矩阵实际编写代码。

<小时/>

更新

为了好玩，我决定尝试编写它，所以这里是测试代码。不过我不会解释其中的逻辑，这需要你自己去理解。

public static void main(String... args) {
    for (int size : new int[] {2,3,4,5,10}) {
        int[][] matrix = createMatrix(size);
        printMatrix(matrix);
        System.out.println();
        rotateMatrix(matrix);
        printMatrix(matrix);
        printSeparatorLine(matrix);
    }
}
private static int[][] createMatrix(int size) {
    int[][] matrix = new int[size][size];
    for (int y = 0, i = 0; y < size; y++)
        for (int x = 0; x < size; x++)
            matrix[y][x] = ++i;
    return matrix;
}
private static void rotateMatrix(int[][] matrix) {
    for (int y1 = 0; y1 < matrix.length / 2; y1++) {
        for (int y2 = matrix.length - y1 - 1, x1 = y1; x1 < y2; x1++) {
            int x2 =  matrix.length - x1 - 1, temp = matrix[y1][x1];
            matrix[y1][x1] = matrix[x2][y1];
            matrix[x2][y1] = matrix[y2][x2];
            matrix[y2][x2] = matrix[x1][y2];
            matrix[x1][y2] = temp;
        }
    }
}
private static void printMatrix(int[][] matrix) {
    int w = maxValueWidth(matrix);
    for (int[] row : matrix) {
        for (int i = 0; i < row.length; i++)
            System.out.printf("%" + (w + (i == 0 ? 0 : 1)) + "d", row[i]);
        System.out.println();
    }
}
private static void printSeparatorLine(int[][] matrix) {
    char[] buf = new char[(maxValueWidth(matrix) + 1) * matrix.length - 1];
    Arrays.fill(buf, '-');
    System.out.println(new String(buf));
}
private static int maxValueWidth(int[][] matrix) {
    return Arrays.stream(matrix).flatMapToInt(Arrays::stream).map(i -> String.valueOf(i).length()).max().getAsInt();
}

输出

1 2
3 4

3 1
4 2
---
1 2 3
4 5 6
7 8 9

7 4 1
8 5 2
9 6 3
-----
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

13  9  5  1
14 10  6  2
15 11  7  3
16 12  8  4
-----------
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

21 16 11  6  1
22 17 12  7  2
23 18 13  8  3
24 19 14  9  4
25 20 15 10  5
--------------
  1   2   3   4   5   6   7   8   9  10
 11  12  13  14  15  16  17  18  19  20
 21  22  23  24  25  26  27  28  29  30
 31  32  33  34  35  36  37  38  39  40
 41  42  43  44  45  46  47  48  49  50
 51  52  53  54  55  56  57  58  59  60
 61  62  63  64  65  66  67  68  69  70
 71  72  73  74  75  76  77  78  79  80
 81  82  83  84  85  86  87  88  89  90
 91  92  93  94  95  96  97  98  99 100

 91  81  71  61  51  41  31  21  11   1
 92  82  72  62  52  42  32  22  12   2
 93  83  73  63  53  43  33  23  13   3
 94  84  74  64  54  44  34  24  14   4
 95  85  75  65  55  45  35  25  15   5
 96  86  76  66  56  46  36  26  16   6
 97  87  77  67  57  47  37  27  17   7
 98  88  78  68  58  48  38  28  18   8
 99  89  79  69  59  49  39  29  19   9
100  90  80  70  60  50  40  30  20  10
---------------------------------------