C++ 7 lines simple solution, 3ms, with explanation


  • 0
    W

    We can view the n x n matrix as n/2 "loops", and rotate each loop respectively. For each loop, we swap elements for each side, and we totally need swap 3 sides to make it rotate 90 degree.
    Note: we only need swap x - 1 elements if the length of side of loop is x.

    Ex: for 4 x 4 matrix which has 2 loops,

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

    Rotate each loop

     1  2  3  4    13  9  5  4     13 9 5 4    13  9 5 1
     5        8     3        8     16     8    16      2
     9       12  => 2       12  => 15    12 => 15      3
    13 14 15 16     1 14 15 16     14 3 2 1    14 12 8 4 
    
     6  7       10 7     10 7      10 6
    10 11  =>   6 11  => 11 6  =>  11 7
    
    class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            int n = matrix.size();
            for(int i = 0; i < n/2; i++) // for each loop
                for(int j = i; j < n - i - 1; j++){
                    swap(matrix[i][j], matrix[n-1-j][i]);
                    swap(matrix[n-1-j][i], matrix[n-1-i][n-1-j]);
                    swap(matrix[n-1-i][n-1-j], matrix[j][n-1-i]);
                }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.