检索放在HashMap中的数组

Question

下面的代码是我为一个问题写的答案,该问题要求将nxn 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)内存占用.

现在我会让你实际编码,对于任何大小的矩阵.

UPDATE

为了它的乐趣,我决定尝试编写它,所以这里是测试代码.我不打算解释这个逻辑,那是你自己弄清楚的.

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