C++ 3ms interesting recursion method with explanation of hand-draw Graph! (O(1) space updated)


  • 1

    0_1486174163434_R60EWN7OI@31KIQA~A$T6@L.png
    First version:

    class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            if(matrix.size() == 0 || matrix.size() == 1)return;
            rotateMatrix(matrix, 0, 0, matrix[0].size());
        }
        //Recursion function, (x,y) is the coordinate of the Top-Left point.  
        //n is the size of current matrix.
        void rotateMatrix(vector<vector<int>>& matrix, int x, int y, int n) {
            if(n == 1|| n == 0) return;
            vector<int>temp1(n - 1);
            vector<int>temp2(n - 1);
            vector<int>temp3(n - 1);
            for(int i = 0; i < n - 1; i++){
                temp1[i] = matrix[x + i][y + n - 1];
                temp2[i] = matrix[x + n - 1][y - i + n - 1];
                temp3[i] = matrix[x - i + n - 1][y];
            }
    
            for(int i = 0; i < n - 1; i++){
                matrix[x + i][y + n - 1] = matrix[x][y + i];
                matrix[x + n - 1][y - i + n - 1] = temp1[i];
                matrix[x - i + n - 1][y] = temp2[i];
                matrix[x][y + i] = temp3[i];
            }
            //Update coordinate of Top-Left point to continue recursion. 
            //Each recursion,the matrix getting smaller by 2 (left col and right col), so it's n-2.
            rotateMatrix(matrix, x + 1, y + 1, n - 2);
        }
    };
    

    Update(08/11/2017):

    I realized I don't have to swap row by row, I can just swap cell by cell, then it would be in place.

    class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            helper(matrix, 0, 0, matrix.size());
        }
        
        void helper(vector<vector<int>>& matrix, int row, int col, int size) {
            if (size == 0 || size == 1) return;
            int step = 0;
            while(step < size - 1){
                swap(matrix[row][col + step], matrix[row + step][col + size - 1]);
                swap(matrix[row][col + step], matrix[row + size - 1 - step][col]);
                swap(matrix[row + size - 1][col + size - 1 - step], matrix[row + size - 1 - step][col]);
                step++;
            }
            helper(matrix, row + 1, col + 1, size - 2);
        }
    };
    

    If above solution confuse you, let me divide the swap operation in detail and explain with a simple example:

    Initial matrix: (Note: a,b,c,d are placed clockwisely)              We want it to be:
       a, b                                                                  d, a
       d, c                                                                  c, b
    

    Operation:
    Assign a to b
    Assign b to c
    Assign c to d
    Assign d to a

    Code:

    class Solution {
    public:
        void rotate(vector<vector<int>>& matrix) {
            helper(matrix, 0, 0, matrix.size());
        }
        
        void helper(vector<vector<int>>& matrix, int row, int col, int size) {
            if (size == 0 || size == 1) return;
            int step = 0;
            int a, b, c, d;
            while (step < size - 1) {
                a = matrix[row][col + step];
                b = matrix[row + step][col + size - 1];
                c = matrix[row + size - 1][col + size - 1 - step];
                d = matrix[row + size - 1 - step][col];
                matrix[row + step][col + size - 1] = a;
                matrix[row + size - 1][col + size - 1 - step] = b;
                matrix[row + size - 1 - step][col] = c;
                matrix[row][col + step] = d;
                step++;
            }
            helper(matrix, row + 1, col + 1, size - 2);
        }
    };
    

    I know reverse row first and swap the symmetry is much simpler, but I do found this solution interesting and shows a "dynammic" process of how matrix rotated "ring" by "ring", so I'd like to share it. Also, my solution doesn't need to reverse the matrix first, so it would be slightly faster, but both solutions are in order of O(n) or O(row * col).


    If you see anything that could be improved, plz let me know~


  • 0
    S

    sry, ,,,,,, in_place?


  • 0
    This post is deleted!

  • 0
    S

    no. I mean the requirement:
    Follow up:
    Could you do this in-place?
    but dose this method meet the requirement?


  • 0

    @sjbetter Oh,sry. Em.. this solution needs 3 temps, so extra space is needed.


  • 0

    @sjbetter So it do accepted, but does not meet the follow up requirement.


  • 0

    @sjbetter hi, sjbetter, I have updated O(1) space version, u can have a look if still interested. Sry i was too noob in problem solving back then...lol, I have updated both version to make them clean and readable.


Log in to reply
 

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