数据结构--旋转数组

数据结构–旋转数组

有一个二维数组，请在不使用额外变量的情况下，完成对其选择90度

分析(旋转遍历法)

找到坐标变化规律

设这个矩阵长宽为N
我们可以知道第一行，将会变为倒数第一列
那么对于第I行，就会变为倒数第I列
对于第J列，就会变成第几行
所以对应关系为[I,J] -> [J,N-1-I] （这里为N-1是因为坐标从0开始所以最大的坐标为N-1）
旋转时每个坐标都有与之对应的3个坐标点,总共4个坐标点相互互换位置
[I,J] -> [J,N-1-I] -> [N-1-I,N-1-J] -> [N-1-J,I] -> [I,J]
所以我们只需要遍历 1/4 的坐标,然后变动对应的 4 组坐标 即可实现全部坐标的替换

两种选择方式

正方形旋转（图1）：
对于N为偶数是便于旋转的，但是如果N为奇数，则不好使用统一的代码来管理（只能旋转图1中的那六个点），对于重复的部分，不能旋转，因为如图所示有一个小正方形，你不能用自己的元素旋转到自己那里
等腰三角形旋转（图2）：
图二的遍历范围为 I(0->N),J(I->N-1-I) 总面积为 N * N/2 * 1/2=N方/4(三角形面积)
相当于把正方形分为 4 个等腰直角三角形
这种分割方式即使 N 为奇数也可以正常等分,图例中可以在每个三角形中取到独占的 6 个点
需要注意的是(0,4),(1,3) 这两个点不能包含起来 所以遍历的时候判断条件不能等于

所以使用图 2 的遍历方式 把遍历到的每个点和与之对应的其他三个点互换值即可实现旋转

实现不使用额外变量

通过：
A = A+B
B = A-B
A = A-B
这三步之后我们就实现了不占用额外的内存空间,交换了 AB 的值

使用位运算
通过使用两次^完成交换

代码实例

有临时变量（自己太菜了）

class Solution {
    public void rotate(int[][] matrix) {
        int length = matrix.length;
        int [][] temp = new int[length][length];
        for(int i = 0;i < length;i++){
        for(int j = length - 1;j >= 0;j--){
            temp[i][length - j - 1] = matrix[j][i];
        }
        }
        for(int i = 0;i < length; i++){
            matrix[i] = Arrays.copyOf(temp[i],length)
        }
    }
}

位运算版本

class Solution {
    public void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length/2; i++) {
            for (int j = i; j < matrix.length - (i + 1); j++) {
                // 相邻交换一次
                matrix[i][j] = matrix[i][j]^matrix[j][matrix.length-1-i];
                matrix[j][matrix.length-1-i] = matrix[i][j]^matrix[j][matrix.length-1-i];
                matrix[i][j] = matrix[i][j]^matrix[j][matrix.length-1-i];
                // 对角交换一次
                matrix[i][j] = matrix[i][j]^matrix[matrix.length-1-i][matrix.length-1-j];
                matrix[matrix.length-1-i][matrix.length-1-j] = matrix[i][j]^matrix[matrix.length-1-i][matrix.length-1-j];
                matrix[i][j] = matrix[i][j]^matrix[matrix.length-1-i][matrix.length-1-j];
                // 相邻交换一次
                matrix[i][j] = matrix[i][j]^matrix[matrix.length-1-j][i];
                matrix[matrix.length-1-j][i] = matrix[i][j]^matrix[matrix.length-1-j][i];
                matrix[i][j] = matrix[i][j]^matrix[matrix.length-1-j][i];
            }
        }
    }
}

旋转遍历法

    public static void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length - 1; i++) {
            for (int j = i; j < matrix.length - 1 - i; j++) {
                exchange(matrix, i, j, j, matrix.length - 1 - i);
                exchange(matrix, i, j, matrix.length - 1 - i, matrix.length - 1 - j);
                exchange(matrix, i, j, matrix.length - 1 - j, i);
            }
        }
    }

    public static void exchange(int[][] matrix, int i1, int j1, int i2, int j2) {
        matrix[i1][j1] = matrix[i1][j1] + matrix[i2][j2];
        matrix[i2][j2] = matrix[i1][j1] - matrix[i2][j2];
        matrix[i1][j1] = matrix[i1][j1] - matrix[i2][j2];
    }
}

旋转遍历法（位运算）

public static void rotate(int[][] matrix) {
        for (int i = 0; i < matrix.length - 1; i++) {
            for (int j = i; j < matrix.length - 1 - i; j++) {
                exchange(matrix, i, j, j, matrix.length - 1 - i);
                exchange(matrix, i, j, matrix.length - 1 - i, matrix.length - 1 - j);
                exchange(matrix, i, j, matrix.length - 1 - j, i);
            }
        }
    }

    public static void exchange(int[][] matrix, int i1, int j1, int i2, int j2) {
        matrix[i1][j1] = matrix[i1][j1] ^ matrix[i2][j2];
        matrix[i2][j2] = matrix[i1][j1] ^ matrix[i2][j2];
        matrix[i1][j1] = matrix[i1][j1] ^ matrix[i2][j2];
    }