48. Rotate Image

Description:

https://leetcode.com/problems/rotate-image/#/description

Algorithm:

4	4	4	4	4
4	->	2	->	4
4	2	0	2	4
4	<-	2	<-	4
4	4	4	4	4

• n is odd (in our example,  n = 5)
  • the central blue one (n/2, n/2) = (2, 2) doesn’t move
  • the k-th outer ring moves clockwise for 2 * k units, the k-th ring contains 8 * k units
    • How to move?
      • row index: i, col index j
      • start from i = n/2 – k, j= n/2 – k and go for the whole ring
      • move right:   if (i < m + k && j == m – k)  i = i + 1, j = j
      • move down: if (i == m + k &&  j < m + k)  j = j + 1, i = i
      • move left:     if (i > m – k && j == m + k)  i = i – 1, j = j
      • move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
    • tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
    • oldIndex = newIndex
• n is even
  • there is no central fixed uint!
  • the k-th outer ring moves clockwise for 2 * k – 1 units, the k-th ring contains 8 * (k – 1) +4 units
    • How to move?
      • row index: i, col index j
      • start from i = n/2 – k, j= n/2 – k and go for the whole ring
      • move right:   if (i < m + k – 1 && j == m – k)  i = i + 1, j = j
      • move down: if (i == m + k – 1 &&  j < m + k – 1)  j = j + 1, i = i
      • move left:     if (i > m – k && j == m + k – 1)  i = i – 1, j = j
      • move up:      if (i == m – k && j > m – k)  j = j – 1, i = i
    • tmp = matrix[newIndex] AND matrix[newIndex] = matrix[oldIndex]
    • oldIndex = newIndex

Code:

class Solution {
public:
void rotate(vector<vector>& matrix) {
int m = matrix.size() / 2;
if (m < 1) return;
if (matrix.size() % 2)
{
for (int k = 1; k <= m; k++)
{
for (int l = 0; l < 2 * k; l++)

              {

                  int elementNum = 8 * k; int i = m - k; int j = m - k; int tmp = matrix[j][i];

                  while (elementNum > 0)
{
int i_new = (i < m + k && j == m - k) ? i + 1 : (i > m - k && j == m + k) ? i - 1 : i;
int j_new = (j < m + k && i == m + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j;
swap(matrix[j_new][i_new], tmp);
i = i_new;
j = j_new;
elementNum--;
}
}
}
}
else
{
for (int k = 1; k <= m; k++)
{
for (int l = 0; l < k * 2 - 1; l++) {

                   int elementNum = 8 * (k - 1) + 4; int i = m - k; int j = m - k; int tmp = matrix[j][i];

                 while (elementNum > 0)
{
int i_new = (i < m - 1 + k && j == m - k) ? i + 1 : (i > m - k && j == m - 1 + k) ? i - 1 : i;
int j_new = (j < m - 1 + k && i == m - 1 + k) ? j + 1 : (j > m - k && i == m - k) ? j - 1 : j;
swap(matrix[j_new][i_new], tmp);
i = i_new;
j = j_new;
elementNum--;
}
}
}
}
}
};


Timing:

Luckily time is good…3ms (fastest)

complexity: O(n)

n is the number of elements.