简介

数组是有序的相同类型的元素序列。一维数组的地址是连续的，二维数组由多组一维数组构成。java是row master存储元素，从下图二维数组的地址分布就可以看出（数据类型为int）

在遍历数组时连续的地址访问会对代码提速，具体会提升多少，这里有一份对比：

数组的元素存储在堆中，引用别名放在栈中，这也就是为什么不同别名可以指向相同地址的数组的原因了

例题

88.合并两个有序数组

https://leetcode-cn.com/problems/merge-sorted-array/
要求空间复杂度为O(1)，时间复杂度为O(N)。

三指针逆序遍历，利用数据结构的特性先将大的值依次从尾部往前放置。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + --n;
        while (n >= 0) {
            nums1[p--] = m>=0 && nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
    }
}

48.旋转图像

https://leetcode-cn.com/problems/rotate-image/
将一个方阵顺时针旋转90°

解决方案，直接能想到的是开辟一个新的同样规模的二维数组，按照规则逐步的赋值，时间复杂度O(n^2)，空间复杂度O(n^2)，这样不是最优的解决方案。
空间复杂度可以降低到O(1)，利用空间变换的特性先将二维数组按照对角线旋转，然后再以中间列为基准左右翻转，仅仅需要引用一个额外变量，时间复杂度也是O(n^2)。

class Solution {
    public void rotate(int[][] matrix) {
        for (int u = 0; u < matrix.length; u++) {
            for (int m = u+1; m < matrix[0].length; m++) {
                if (u == m) {
                    continue;
                }
                int temp = matrix[m][u];
                matrix[m][u] = matrix[u][m];
                matrix[u][m] = temp;
            }
        }
        for (int u = 0; u < matrix.length; u++) {
            for (int m = matrix[0].length-1; m >= matrix[0].length/2; m--) {
                int temp = matrix[u][m];
                matrix[u][m] = matrix[u][matrix[0].length-1-m];
                matrix[u][matrix[0].length-1-m] = temp;
            }
        }
    }
}

35.搜索插入位置

https://leetcode-cn.com/problems/search-insert-position/
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) {
            return 0;
        }
        int s = 0;
        int e = nums.length-1;
        while (s<=e) {
            int ind = (e+s)/2;
            if (nums[ind] > target) {
                e = ind-1;
            } else if (nums[ind] < target) {
                s = ind+1;
            } else {
                return ind;
            }
        }
        return s;
    }
}

73.矩阵置零

https://leetcode-cn.com/problems/set-matrix-zeroes/
在二维数组中，将零元素所在的同行和同列的元素都置零。

最简单的办法就是单独用一行和一列记录行列是否有零，最后将对为零的行、列置零。时间复杂度O(mn)，空间复杂度O(m+n)

换个思路，将用于标记行列的数组放在数组的第一行和第一列上，这样我们可以将空间复杂度压缩到O(1)。

// 时间复杂度 O(mn)  空间复杂度O(m+n)
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }
}

// 时间复杂度 O(mn)  空间复杂度O(1)
class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        boolean flagCol0 = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                flagCol0 = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (flagCol0) {
                matrix[i][0] = 0;
            }
        }
    }
}