3

与えられた 2D NxN 行列を同心円として視覚化します。円内の各要素が時計回りと反時計回りの交互の方向にレイヤーごとに 1 位置ずつ回転する回転行列を見つける必要があります。すべての回転は所定の位置にある必要があります。

2 3 4 5
1 6 7 8
4 2 1 9
5 3 2 4

に変換する必要があります

1 2 3 4 
4 7 1 5 
5 6 2 8 
3 2 4 9

解決策を考えた

1>時計回りの円の回転の場合、要素を順番に読み取ります

i -> 0 to n-1 and j = 0
j -> 0 to n-1 and i = n-1
i -> n-1 to 0 and j = n-1
j -> n-1 to 0 and i = 0

2>反時計回りの円の回転の場合、要素を順番に読み取ります

j -> 0 to n-1 and i = 0
i -> 0 to n-1 and j = n-1
j -> n-1 to 0 and i = n-1
i -> n-1 to 0 and j = 0

コード

for(int cnt = 0; cnt < n/2; cnt++)
    {   
        if(cnt%2 == 0) // Clockwise
        {   
            i = cnt; j = cnt;
            // while loops for each case
        }
        else // anti-clockwise
        {
            i = cnt; j = cnt;
            // while loops for each case
        }       
}

この問題を O(n2) 以上で解決するためのより良い方法はありますか?

4

6 に答える 6

1

最近、就職の面接でこの問題に直面しましたが、1 時間以内に解決できませんでした。

それから家に帰って、Javaで以下のコードを作成しました。これは再帰的であり、O(n^2) の複雑さがあると思います。ここでもコードを確認できます: https://github.com/lotif/rotateMatrix

最初に (正方形) マトリックスの次元を入力し、次にマトリックス自体の数をスペースで区切って行ごとに入力する必要があります。例えば：

3

1 2 3

4 5 6

7 8 9

同心円で時計回りに回転した行列が返されます。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class RotateMatrix {

    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);

        int d = s.nextInt();

        int[][] matrix = new int[d][d];
        for(int i = 0; i < d; i++) {
            for(int j = 0; j < d; j++) {
                matrix[i][j] = Integer.parseInt(s.next());
            }
        }

        matrix = rotate(matrix);

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

        s.close();
    }

    public static int[][] rotate(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix.length == 1) {
            return matrix;
        }

        List<Integer> outerCircle = getOuterCircle(matrix);
        matrix = removeOuterCircle(matrix);
        //rotating outer circle
        outerCircle.add(0, outerCircle.remove(outerCircle.size() - 1));

        matrix = rotate(matrix);

        matrix = addOuterCircle(outerCircle, matrix);

        return matrix;

    }

    private static int[][] addOuterCircle(List<Integer> outerCircle, int[][] matrix) {

        int d = matrix.length + 2;
        int[][] newMatrix = new int[d][d];

        //Adding the outer circle to the matrix
        for(int j = 0; j < d; j++) {
            newMatrix[0][j] = outerCircle.remove(0);
        }
        for(int i = 1; i < d; i++) {
            newMatrix[i][d-1] = outerCircle.remove(0);
        }
        for(int j = d-2; j >= 0; j--) {
            newMatrix[d-1][j] = outerCircle.remove(0);
        }
        for(int i = d-2; i >= 1; i--) {
            newMatrix[i][0] = outerCircle.remove(0);
        }

        //Adding the inner matrix
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                newMatrix[i + 1][j + 1] = matrix[i][j];
            }
        }

        return newMatrix;

    }

    private static List<Integer> getOuterCircle(int[][] matrix) {
        int d = matrix.length;

        List<Integer> outerCircle = new ArrayList<Integer>();

        for(int j = 0; j < d; j++) {
            outerCircle.add(matrix[0][j]);
        }
        for(int i = 1; i < d; i++) {
            outerCircle.add(matrix[i][d-1]);
        }
        for(int j = d-2; j >= 0; j--) {
            outerCircle.add(matrix[d-1][j]);
        }
        for(int i = d-2; i >= 1; i--) {
            outerCircle.add(matrix[i][0]);
        }

        return outerCircle;
    }

    private static int[][] removeOuterCircle(int[][] matrix) {      
        int d = matrix.length;
        int[][] newMatrix = new int[d-2][d-2];

        for(int i = 1; i < d-1; i++) {
            for(int j = 1; j < d-1; j++) {
                newMatrix[i-1][j-1] = matrix[i][j];
            }
        }

        return newMatrix;
    }

}
于 2015-09-18T17:33:15.897 に答える
0 
public class ShiftArray {
    static void shiftArray(int[][]a, int index, int n) {
       if ((n%2 == 0) && (index >= n/2))
           return;
       if ((n%2 != 0) && (index > n/2))
           return;

       int tempRowTopLast = a[index][n-1-index]; 
       int tempColRightLast = a[n-1-index][n-1-index];
       int tempRowBottomLast = a[n-1-index][index]; 
       int tempColLeftLast = a[index][index];

       int temp, temp2;

       temp = tempColLeftLast; 

       for (int k = index + 1; k < n-index; k++) {
           temp2 = a[index][k];
           a[index][k] = temp;
           temp = temp2;
       }

       temp = tempRowTopLast; 
       for (int k = index + 1; k < n-index; k++) {
           temp2 = a[k][n-1-index];
           a[k][n-1-index] = temp; 
           temp = temp2; 
       }

       temp = tempColRightLast; 
       for (int k = n-2-index; k >=index; k--) {
           temp2 = a[n-1-index][k];
           a[n-1-index][k] = temp; 
           temp = temp2; 
       }

       temp = tempRowBottomLast;
       for (int k = n-2-index; k >=index; k--) {
           temp2 = a[k][index];
           a[k][index] = temp;
           temp = temp2;
       } 

       shiftArray(a, index+1, n);

    }

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

        shiftArray(a, 0, 3);
        System.out.println("Rotated array...");

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(a[i][j] + ",");
            }
            System.out.println();
       }
    }
}
于 2015-01-13T09:05:44.677 に答える