数据结构-稀疏矩阵快速转置（Java代码）

解题思路:

1.首先先将原始数组转化为稀疏矩阵

2.在稀疏矩阵中，交换每一行的第一列和第二列，第三列不变，也就是交换了原始矩阵的行列

3.建立一个新的数组

4.将稀疏矩阵中的值放入新的数组中即可

注意事项:

1. 首先你的了解稀疏矩阵的结构

2. 在创建新矩阵的同时，要记得交换行和列(在创建的时候就交换了)
   

参考代码:

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

     int row = scanner.nextInt();//矩阵的行

     int col = scanner.nextInt();//矩阵的列

     int arr[][] = new int[row][col];//原始的矩阵

     //初始化原始矩阵

     for (int i = 0; i < arr.length; i++) {

          for (int j = 0; j < arr[i].length; j++) {

         arr[i][j] = scanner.nextInt();

          }

     }

     //将二维数组转化为稀疏数组

     /*

     * 思路：

     * 1.获取原始二维数组的行数和列数

     * 2.统计非0的个数

     * 3.创建稀疏数组

     */

     int sum = 0;//统计非0的个数

     for (int[] i : arr) {

          for (int data : i) {

              if(data != 0) {

              sum++;

             }

         }

     }

     //创建稀疏矩阵

     int sparesArray[][] = new int[sum+1][3];

     //初始化稀疏矩阵的第一行

     sparesArray[0][0] = row;

     sparesArray[0][1] = col;

     sparesArray[0][2] = sum;

     int k = 1;//用来控制稀疏矩阵的行

     //将原始数组非0的位置以及数据存入稀疏数组中

     for (int i = 0; i < arr.length; i++) {

         for (int j = 0; j < arr[i].length; j++) {

             if(arr[i][j] != 0) {

                 sparesArray[k][0] = i;

                 sparesArray[k][1] = j;

                 sparesArray[k][2] = arr[i][j];

                     k++;

                 }

             }

     }

     //将稀疏矩阵第一列和第二列的数据交换，之后再还原为二维数组，实现快速倒置(从稀疏矩阵的第二行开始)

     //1.稀疏矩阵的一二列交换

     int temp = 0;//用来存放中间数据

     for (int i = 1; i < sparesArray.length; i++) {

         temp = sparesArray[i][0];

         sparesArray[i][0] = sparesArray[i][1];

         sparesArray[i][1] = temp;

     }

     //2.还原为二维数组

     int newArray[][] = new int[sparesArray[0][1]][sparesArray[0][0]];//因为倒置，所以行列要交换

     for (int i = 1; i < sparesArray.length; i++) {

         newArray[sparesArray[i][0]][sparesArray[i][1]] = sparesArray[i][2];

     }

     //输出倒置的二维数组

     for (int[] i : newArray) {

         for (int data : i) {

             System.out.print(data+" ");

         }

         System.out.println();

     }

}