Objective : We will be given one 2D array we need to rotate the array by 90 degree or by given degree.
There can be 2 type of implementation we can do for this problem solution
- Novice Solution , we will create one array and fill the array according to the degree provided.
- In Place Rotation in which we will change the value in same array only.
Implementation : Using Temp Array for Rotation:
public class R2 { public static void main(String[] args) { // NOTE: The following input values will be used for testing your solution. int a1[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // rotate(a1, 3) should return: // [[7, 4, 1], // [8, 5, 2], // [9, 6, 3]] int a2[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; // rotate(a2, 4) should return: // [[13, 9, 5, 1], // [14, 10, 6, 2], // [15, 11, 7, 3], // [16, 12, 8, 4]] } // Implement your solution below. public static int[][] rotate(int[][] a, int n) { int[][] rotated = new int[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { rotated[j][n - 1 - i] = a[i][j]; } } return rotated; } }
The Space Complexity of this approach is higher than the new approach , Let see the new Approach.
Second Way : Using Inplace Rotation way
Second Way : Using Inplace Rotation way
public class R2InPlace { public static void main(String[] args) { // NOTE: The following input values will be used for testing your solution. int a1[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; // rotate(a1, 3) should return: // [[7, 4, 1], // [8, 5, 2], // [9, 6, 3]] int a2[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}; // rotate(a2, 4) should return: // [[13, 9, 5, 1], // [14, 10, 6, 2], // [15, 11, 7, 3], // [16, 12, 8, 4]] } // Implement your solution below. public static int[][] rotate(int[][] a, int n) { // n/2 gives us floor(n/2) // and n/2 + n%2 gives us ceiling(n/2) for (int i = 0; i < n / 2 + n % 2; i++) { for (int j = 0; j < n / 2; j++) { int[] tmp = new int[4]; int currentI = i; int currentJ = j; for (int k = 0; k < 4; k++) { tmp[k] = a[currentI][currentJ]; int[] newCoordinates = rotateSub(currentI, currentJ, n); currentI = newCoordinates[0]; currentJ = newCoordinates[1]; } for (int k = 0; k < 4; k++) { a[currentI][currentJ] = tmp[(k + 3) % 4]; int[] newCoordinates = rotateSub(currentI, currentJ, n); currentI = newCoordinates[0]; currentJ = newCoordinates[1]; } } } return a; } public static int[] rotateSub(int i, int j, int n) { int[] newCoordinates = new int[2]; newCoordinates[0] = j; newCoordinates[1] = n - 1 - i; return newCoordinates; } }
I hope this will help you in solving the problem, If you like this post , please share with your friends and colleagues.
Thanks for reading
Noeik
0 comments:
Post a Comment