leetcode 48 :画像を回転する

問題文:
画像を表すN x N 2 D行列を与え、画像を90度回転させます.
あなたは、直接入力2 Dマトリックスを変更する必要があることを意味場所で画像を回転させる必要があります.別の2 Dマトリックスを割り当てて、回転をしないでください.

テストケース
例1 :

入力:行列=[ [ 1 , 2 , 3 ], [ 4 , 5 , 6 ], [ 7 , 8 , 9 ]
出力:[ [ 7 , 4 , 1 ], [ 8 , 5 , 2 ], [ 9 , 6 , 3 ]
例2 :

入力:行列=[ [ 5 , 1 , 9 , 11 ], [ 2 , 4 , 8 , 10 ], [ 13 , 3 , 6 , 7 ], [ 15 , 14 , 12 , 16 ]
出力:[ 15 , 13 , 2 , 5 ], [ 14 , 3 , 4 , 1 ], [ 12 , 6 , 8 , 9 ], [ 16 , 7 , 10 , 11 ]
例3 :
入力:マトリックス= [ 1 ]
出力:[ 1 ]
例4 :
入力:マトリックス= [ [ 1 , 2 ]、[ 3 , 4 ] ]
出力:[ [ 3 , 1 ], [ 4 , 2 ] ]

制約
マトリックス.長さ== N マトリックス[ I ].長さ== N

1 <= n <= 20

- 1000 <>マトリックス[ i ][ j ] <= 1000

アルゴリズム
単純なアイデアは、この行列

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

1 2 3
4 5 6
7 8 9

Just take the transpose and lets see what we got :

1 2 3           1 4 7
4 5 6.      =>  2 5 8   
7 8 9           3 6 9

So we got the above after doing the transpose operation.

for (int i=0; i<row; i++) {
            for (int j=0; j<i; j++) {
                swap(matrix, i, j);
            }
        }

Now let's compare it with our possible answer.
Our transpose is :

1 4 7                            7 4 1
2 5 8.     and our answer is     8 5 2
3 6 9                            9 6 3

So what we observe, answer is just reversing each row after doing the transpose.

1 4 7. after reversing 7 4 1
2 5 8  after reversing 8 5 2
3 6 9  after reversing 9 6 3

which is what we needed as our answer.

したがって、アルゴリズムはとても簡単です.
1 )与えられた行列の置き換えを取る
2 )各行逆転

Note : The above is 90 degree clockwise direction. What if, we need to rotate 90 degree anti clockwise direction.

Same way, just take the transpose.

1 2 3           1 4 7
4 5 6.      =>  2 5 8   
7 8 9           3 6 9

Now what will be our possible answer if we do anti clockwise 90 degree rotation on given matrix.

1 2 3           3 6 9
4 5 6.      =>  2 5 8   
7 8 9           1 4 7

Now we can just observe the answer along with the transpose of the matrix

1 4 7                            3 6 9
2 5 8.     and our answer is     2 5 8
3 6 9                            1 4 7

So we can observe that if we just reverse all the column, we will get the desired output.

1 4 7. after reversing column wise 3 6 9
2 5 8                              2 5 8
3 6 9                              1 4 7

複雑性
時間の複雑さはo(row * col)であり、我々が適所にやっているので、空間の複雑さはo(1)である.

コード:時計回り90度回転

class Solution {
    public void rotate(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        for (int i=0; i<row; i++) {
            for (int j=0; j<i; j++) {
                swap(matrix, i, j);
            }
        }
        for (int [] rowWise : matrix) {
            reverse(rowWise, 0, col - 1);
        }
    }

    private void swap(int [][] matrix, int i, int j) {
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }

    private void reverse(int [] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

ギタブ

Rohithv07 / LeetCode
解決されるleetcode問題.
LeetCode
解決されるleetcode問題.

View on GitHub

Rohithv07 / LeetCodeTopInterviewQuestions
Leetcodeで議論されるLeetcodeトップインタビュー質問.https://leetcode.com/explore/interview/card/top-interview-questions
leetcodetopInterview質問
Leetcodeで議論されるLeetcodeトップインタビュー質問.https://leetcode.com/explore/interview/card/top-interview-questions-easy/
また、codesignalから答えられる質問.コム:https://app.codesignal.com/

View on GitHub