转置矩阵

转置矩阵_LeetCode867

题目

给你一个二维整数数组 matrix， 返回 matrix 的 转置矩阵 。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[1,4,7],[2,5,8],[3,6,9]]
示例 2：

输入：matrix = [[1,2,3],[4,5,6]]
输出：[[1,4],[2,5],[3,6]]

解法

第一种解法

public static int[][] transpose(int[][] matrix) {
    for (int i = 0; i < matrix.length; i++) {
        for (int j = i + 1; j < matrix.length; j++) {
            matrix[i][j] = matrix[i][j] ^ matrix[j][i];
            matrix[j][i] = matrix[i][j] ^ matrix[j][i];
            matrix[i][j] = matrix[i][j] ^ matrix[j][i];
        }
    }
    return matrix;
}

这种解法错误,因为只考虑了行数和列数相等的情况,没有考虑行数和列数不相等的二维数组

第二种解法

public static int[][] transpose(int[][] matrix) {
    int[][] temp = new int[matrix[0].length][matrix.length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            temp[j][i] = matrix[i][j];
        }
    }
    return temp;
}

这种解法能通过,但是内存消耗比较大,因为是先创建了一个数组,然后对原数组中的每个元素遍历确定位置

第三种解法

public static int[][] transpose(int[][] matrix) {
    int c = matrix[0].length;
    int r = matrix.length;
    int[][] temp = new int[c][r];
    for (int i = 0; i < r * c; i++) {
        temp[i/r][i%r] = matrix[i%r][i/r];
    }
    return temp;
}

这种解法巧妙的运用到了取余和模除两种,但是在空间复杂度上和第二种类似,由于数组具有不可变性,因此想要实现空间复杂度小的代码很难实现.