Write an algorithm to rotate matrix nxm clockwise 90 degree.
Use no compiler, no Ctrl+C, and then, time complexity analysis:
Here is the code Julia wrote, she thought about the swapping strategies:
1. swap multiple times
2. leave four corners as is, swap four corners seperately.
https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d
/*
April 5, 2016
NO ctrl+C copy
matrix nxm rotate clockwise 90 degree
do it in place
*/
public static bool rotateInplace90ClockWise(int[][] arr)
{
if (arr == null || arr.Length == 0 || arr[0].Length == 0) return false;
int n = arr.Length; // row
int m = arr[0].Length; // column
if (n != m) return false;
// we need to start loops
int start = 0;
int end = n - 1;
while (start < end && start < n / 2 && end < n / 2)
{
// top with right swap - left the terminal point untouched
// left to right <- row
// top to down <- column
for (int i = start + 1; i < end - 1; i++)
{
int currx = start;
int curry = i;
int currx_col = i;
int curry_col = end;
swap(arr, currx, curry, currx_col, curry_col);
}
// now, top down, we need to cross swap
for (int i = start + 1; i < end - 1; i++)
{
int currx = start;
int curry = i;
int currx_down = end;
int curry_down = end - i;
swap(arr, currx, curry, currx_down, curry_down);
}
// left and top swap
for (int i = start + 1; i < end - 1; i++)
{
// left part
int currx = end - 1 - i;
int curry = start;
int currx_top = start;
int curry_top = i;
swap(arr, currx, curry, currx_top, curry_top);
}
// and then, rotate four corners
// 1, 2
// 4 3
swap(arr, start, start, start, end);
swap(arr, end, end, start, start);
swap(arr, start, start, end, start);
start++;
end--;
}
return true;
}
private static void swap(int[][] arr, int x, int y, int x2, int y2)
{
int tmp = arr[x][y];
arr[x][y] = arr[x2][y2];
arr[x2][y2] = tmp;
}
https://gist.github.com/jianminchen/e489cf7a490ac426eb50b4300890387d
time complexity: since every node in the matrix at most swaps twice, so the count of swap is O(n^2)
