Share my 11line C++ code without extra space and needs less than n*2 time


  • 3
    C
     class Solution {
        public:
            void rotate(vector<vector<int> > &matrix) {
                int n = matrix.size();
                for(int i = 0; i < n-1; ++i)
                    for(int j = 0; j < n-1-i;++j)
                        swap(matrix[i][j],matrix[n-j-1][n-i-1]);
                for(int i = 0; i < n/2; ++i)
                    for(int j = 0; j < n; ++j)
                        swap(matrix[i][j],matrix[n-1-i][j]);
            }
        };
    
    
    
          I discovered the fact that rotating the matrix 90 degrees can be solve by swapping some elements of the matrix twice.
         For example
        1 2 3     9 6 3
        4 5 6 ->  8 5 2  (swap the elements which are symmetric to the line from left-down to right-top)
        7 8 9     7 4 1
        then swap the line horizontally (swap line-0 and line-2), and we got the result
        7 4 1 
        8 5 2
        9 6 3

  • 0
    T

    very brilliant solution!


  • 0
    M

    You are a real genius


  • 0
    C

    I think you code's computation complexity is exactly N^2.
    Less than N^2 time is not correct.


Log in to reply
 

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