CareerCup 150

C.C 1.6

/**
 *
 * 1.6 Given an image represented by an NxN matrix, where each pixel in the
 * image is 4 bytes, write a method to rotate the image by 90 degrees. Can you
 * do this in place?
 *
 * @author Jiateng
 */
public class CC1_6 {

    //Time O(n), Space O(n)
    public static void rotate1(int[][] image) {
        if (image == null) {
            return;
        }
        //NxN will be a square
        int len = image.length;

        int[][] result = new int[len][len];

        //result is the rotated 90 degree image
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                result[j][len - i - 1] = image[i][j];
            }
        }

        //set the result to the image
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                image[i][j] = result[i][j];
            }
        }
    }

    //Time O(n), Space O(1), no extra space
    public static void rotate2(int[][] image) {
        if (image == null) {
            return;
        }

        int len = image.length;
        /**
         * these two for loop.
         *
         * i: 0~len/2, j: len-i-1. from 0 to half of the len. every time i + 1,
         * j will be start from i, and less 2 than the previous j.
         *
         * means that loop the elements in the top quadrant.
         *
         * Then rotate the rest three quadrants.
         */
        for (int i = 0; i < len / 2; i++) {
            for (int j = i; j < len - i - 1; j++) {
                int temp = image[i][j];
                image[i][j] = image[len - j - 1][i];
                image[len - j - 1][i] = image[len - i - 1][len - j - 1];
                image[len - i - 1][len - j - 1] = image[j][len - i - 1];
                image[j][len - i - 1] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] image = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        //rotate1(image);
        rotate2(image);

        for (int i = 0; i < image.length; i++) {
            for (int j = 0; j < image[0].length; j++) {
                System.out.print(image[i][j] + " ");
            }
            System.out.println(" ");
        }
    }
}