数组之稀疏数组

稀疏数组,程序员听了,难道冥冥之中是天意?和头发一样的稀疏。

---

其实不然，例如：下棋的棋盘（11*11），用二维数组表示，

image.png

二维数组中的无效数据太多了，这么多0毫无意义。

---

稀疏数组诞生了。可以将数组转换为：

image.png

我们可以发现稀疏数组可以大幅减少空间的使用。

细数数组的特性：

• 行的数量等于元素个数+1，只有三列
• 第一行描述：-第1行，第1列：原数组的行，第1行，第2列：原数组的列， 第1行，第3列：原数组的值的个数
• 接下来就是描述原数组行和列，以及值（row，col，val）

普通二维数组转化为稀疏数组：

• 要得到原数组值的个数和 sum
• 创建稀疏数组int [][] sparse = new int[sum+1][]
• 原数组对应的信息存入稀疏数组

了解了特性和方法之后我们来代码实现：

public class SparseArray {
    public static void main(String[] args) {
        // 创建二维数组,棋盘是11*11的
        int[][] array = new int[11][11];
        // 1代表黑子,2代表白子
        array[1][2] = 1;
        array[2][3] = 2;
        // 遍历二维数组
        for (int[] is : array) {
            for (int x : is) {
                System.out.print(x + "\t");
            }
            System.out.println();
        }
        /*
         * 稀疏数组,固定的是三列,第一列是原来二维数组行的值,第二列是原来二维数组列的值,第三列是二维数组的值 row col value
         */
        // 获取二维数组值的个数
        int sum = 0;
        for (int i = 0; i < 11; i++) {
            for (int j = 0; j < 11; j++) {
                if (array[i][j] != 0) {
                    sum++;
                }
            }
        }
        System.out.println(sum);
        // 创建稀疏数组
        int count = 0;
        int[][] sparseArray = new int[sum + 1][3];
        // 给稀疏数组第一行复制,数组行的个数,列的个数,非零的个数
        sparseArray[0][0] = 11;
        sparseArray[0][1] = 11;
        sparseArray[0][2] = sum;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = array[i][j];
                }
            }
        }
        // 遍历稀疏数组
        for (int[] is : sparseArray) {
            for (int x : is) {
                System.out.print(x + "\t");
            }
            System.out.println();
        }
  }
}

当然还有运行结果:

image.png

聪明的你当然也知道如何将稀疏数组转化为普通数组了吧~