An intuitive solution and an in-place solution, both accepted as best submission in C, well-explained


  • 0

    Rotating 90 degrees clockwise is actually put the first row to the last column, the second row to the last-1 column and so on; the first solution is using an assistant array to store the rotated results and then copy it back. Very simple and intuitive.


    //AC - 0ms;
    void rotate(int** matrix, int rSize, int cSize)
    {
        int** matrix0 = (int**)malloc(sizeof(int*)*rSize);
        for(int i = 0; i < rSize; i++)
            matrix0[i] = (int*)malloc(sizeof(int)*cSize);
        for(int r = 0; r < rSize; r++)
            for(int c = 0; c < cSize; c++)
                matrix0[c][cSize-r-1] = matrix[r][c];
        for(int r = 0; r < rSize; r++)
            for(int c = 0; c < cSize; c++)
                matrix[r][c] = matrix0[r][c];
    }
    

    The second in-place solution will require some logical calculation, since it's a matrix the rowSize==colSize; there are three subproblems we need to handle here:

    • position matrix[r][c] should be rotated to where? Draw a three-dimension matrix in a paper and calculate the rotated equation: matrix[r][c] -> matrix[c][size-r-1] -> matrix[size-r-1][size-c-1] -> matrix[size-c-1][r] -> matrix[r][c], very intuitive and easy;
    • how many circles are there to rotate? Since one circle rotation will affect two rows (the uppermost and the lowermost, of course including the leftmost and rightmost columns) then there will be size/2 circles only for rotation circles - range will be [0, size/2];
    • in each rotation circle, the range should also be determined; this is just like an onion after one circle rotation there will be a round elements disappear and the range will also be squeezed from both sides [r, size-r-1] will be the whole range then;

    void swap(int* p, int* q)
    {
        int t = *p;
        *p = *q;
        *q = t;
    }
    //AC - 0ms;
    void rotate(int** matrix, int rSize, int cSize)
    {
        int t = 0;
        for(int r = 0; r < rSize/2; r++) //only half rows should be set as rotating start;
            for(int c = r; c < cSize-r-1; c++) //the rotating area is shrinking as rotation goes on;
            {
                int t = matrix[r][c];
                swap(&t, &matrix[c][cSize-r-1]);
                swap(&t, &matrix[cSize-r-1][cSize-c-1]);
                swap(&t, &matrix[cSize-c-1][r]);
                swap(&t, &matrix[r][c]);
            }
    }

Log in to reply
 

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