作者：whisper

链接：http://proprogrammar.com:443/article/223

声明：请尊重原作者的劳动，如需转载请注明出处

    前面的章节中，我们已经了解了一维数组。然而，有时候，我们可能需要用到多维数组，它更适合像表或矩阵这样更复杂的结构。

    本章节中，我们将重点围绕二维数组来解释：

• 多维数组是如何工作的？
• 如何运用二维数组来解决问题？

    二维数组简介

    类似于一维数组，二维数组也是由元素的序列组成。但是这些元素可以排列在矩形网格中而不是直线上。

    示例

    让我们来看一个使用二维数组的例子：

// "static void main" must be defined in a public class.
public class Main {
    private static void printArray(int[][] a) {
        for (int i = 0; i < a.length; ++i) {
            System.out.println(a[i]);
        }
        for (int i = 0; i < a.length; ++i) {
            for (int j = 0; a[i] != null && j < a[i].length; ++j) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        System.out.println("Example I:");
        int[][] a = new int[2][5];
        printArray(a);
        System.out.println("Example II:");
        int[][] b = new int[2][];
        printArray(b);
        System.out.println("Example III:");
        b[0] = new int[3];
        b[1] = new int[5];
        printArray(b);
    }
}

    原理

    在一些语言中，多维数组实际上是在内部作为一维数组实现的，而在其他一些语言中，实际上根本没有多维数组。

    1. C++ 将二维数组存储为一维数组。

    下图显示了大小为 M * N 的数组 A 的实际结构：

    因此，如果我们将 A 定义为也包含 M * N 个元素的一维数组，那么实际上 A[i][j] 就等于 A[i * N + j]。

    2. 在Java中，二维数组实际上是包含着 M 个元素的一维数组，每个元素都是包含有 N 个整数的数组。

    下图显示了 Java 中二维数组 A 的实际结构：

    动态二维数组

    与一维动态数组类似，我们也可以定义动态二维数组。 实际上，它可以只是一个嵌套的动态数组。 你可以自己尝试一下。

    算法说明

    对角线遍历

给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素，对角线遍历如下图所示。

 

示例:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

输出:  [1,2,4,7,5,3,6,8,9]

解释:

说明:

1. 给定矩阵中的元素总数不会超过 100000 。 

// 想法：第一第二维索引不应该超出范围，当j >= length, i + 1,当i < 0, j + 1，当 i >= length，j + 1,当j < 0，i+1，
    // 注意这四个判断的顺序, 当i+j是偶数时，向右上，当i+j是奇数时，向左下
    public int[] findDiagonalOrder(int[][] matrix) {
        if(null == matrix || matrix.length == 0){
            return new int[0];
        }
        
        int[] result = new int[matrix.length * matrix[0].length];
        int i = 0;
        int j = 0;
        int k = 0;
        
        while(k < result.length){
            if(0 <= i && i < matrix.length && 0 <= j && j < matrix[0].length){
                result[k++] = matrix[i][j];
                if((i + j) % 2 == 0){
                    j++;
                    i--;
                }else{
                    j--;
                    i++;
                }
            }else if(j >= matrix[0].length){
                j--;
                i += 2;
            }else if(i < 0){
                i++;
            }else if(i >= matrix.length){
                i--;
                j += 2;
            }else if(j < 0){
                j++;
            }
        }
        
        return result;
    }

     找到上面的规则，按规则处理就可以了

    再看下面一个类似的算法

​
public int[] findDiagonalOrder(int[][] matrix) {
        if(matrix.length<1)
            return new int[]{};
        int row=matrix.length;
        int col=matrix[0].length;
        int []result=new int[row*col];
        int r=0;
        int c=0;
        int i=0;
        while(i<row*col){
            while(r>=0 && c<col){
                result[i++]=matrix[r--][c++];
            }
           if(c>=col)
           {
               r+=2;
               c-=1;
           }
           else{
                r+=1;
            }
            while(r<row && c>=0){
                result[i++]=matrix[r++][c--];
            }
            if(r>=row){
                r-=1;
                c+=2;
            }
            else{
                c+=1;
            }
        }
       return result;
    }

​

    这个算法就是先向左上，再向右下，找个规则就可以了

    螺旋矩阵

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

输入:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]

示例 2:

输入:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]

​
// 想法：对行列i,j，当j>当前范围，j--,i++，当j<当前范围，j++,i--，当i>当前范围，i--,j--,当i<当前范围，本轮循环结束，
    // 第一轮范围为0~m-1,0~n-1，以后每轮下限加1，上限减1
    public List<Integer> spiralOrder(int[][] matrix) {
       if(matrix == null){
            return null;
        }
        
        if(matrix.length == 0){
            return new ArrayList<Integer>();
        }
        
        List<Integer> result = new ArrayList<>();
        int rowDown = 0, rowUp = matrix.length - 1, columnDown = 0, columnUp = matrix[0].length - 1, i = 0, j = 0;
        int direction = 1;
        boolean roundStart = true;
        while(rowDown <= rowUp && columnDown <= columnUp){
            if(i >= rowDown && i <= rowUp && j >= columnDown && j <= columnUp){
                if(i == rowDown && j == columnDown){
                    if(roundStart){
                        roundStart = false;
                        result.add(matrix[i][j]);
                    }
                }else{
                    result.add(matrix[i][j]);
                }
                    
                
                if(direction == 1){
                    j++;
                }else if(direction == 2){
                    i++;
                }else if(direction == 3){
                    j--;
                }else{
                    i--;
                }
            }else if(rowDown == rowUp){
            	break;
            }else if(j > columnUp){
                j--;
                i++;
                direction = 2;
            }else if(columnDown == columnUp){
            	break;
            }else if(j < columnDown){
                j++;
                i--;
                direction = 4;
            }else if(i > rowUp){
                i--;
                j--;
                direction = 3;
            }else{
                rowDown++;
                rowUp--;
                columnDown++;
                columnUp--;
                i = rowDown;
                j = columnDown;
                direction = 1;
                roundStart = true;
            }
        }
        
        return result;
    }

​

    每轮处理四个角为rowDown,rowUp,columnDown,columnUp的长方形上的元素，但起点只用处理一次，所以用了个roundStart标记一下，同时规定了一下方向direction，当检索到拐角时下个方向是什么样的

    再看一种比较直观的算法

public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix == null || matrix.length == 0)
    		return list;
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0; 

        //统计矩阵从外向内的层数，如果矩阵非空，那么它的层数至少为1层
        int count = (Math.min(m, n)+1)/2;
        //从外部向内部遍历，逐层打印数据
        while(i < count) {
        	for (int j = i; j < n-i; j++) {
				list.add(matrix[i][j]);
			}
        	for (int j = i+1; j < m-i; j++) {
				list.add(matrix[j][(n-1)-i]);
			}
        	
        	for (int j = (n-1)-(i+1); j >= i && (m-1-i != i); j--) {
				list.add(matrix[(m-1)-i][j]);
			}
        	for (int j = (m-1)-(i+1); j >= i+1 && (n-1-i) != i; j--) {
				list.add(matrix[j][i]);
			}
        	i++;
        }    
        return list;
    }
}

    算了一个轮数，再用四个for循环计算四个方向，很直观的算法

    杨辉三角

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

​
// 想法：中学的杨辉三角，根据性质通过上一行算下一行
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp;
        List<Integer> pre;
        
        if(numRows == 0){
            return result;
        }else if(numRows == 1){
            temp = new ArrayList<>();
            temp.add(1);
            result.add(temp);
            return result;
        }
        
        temp = new ArrayList<>();
        temp.add(1);
        result.add(temp);
        for(int i = 1; i < numRows; i++){
            temp = new ArrayList<>();
            temp.add(1);
            pre = result.get(i - 1);
            for(int j = 0; j < pre.size() - 1; j++){
                temp.add(pre.get(j) + pre.get(j + 1));
            }
            
            temp.add(1);
            result.add(temp);
        }
        
        return result;
    }

​

    再来看一种算法

public List<List<Integer>> generate(int numRows) {
        if (numRows <= 0) {
            return new ArrayList<>(0);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>(i+1);
            for (int j = 0; j < i + 1; j++) {
                if (j == 0 || j == i) {
                    list.add(1);
                    continue;
                }
                List<Integer> preList = result.get(i - 1);
                int t = preList.get(j-1) + preList.get(j);
                list.add(t);
            }
            result.add(list);
        }
        return result;
    }

    思路类似，但代码更加紧凑

亲爱的读者：有时间可以点赞评论一下