CHARLIE SAYS

数组是一种连续存储的线性结构：元素类型相同、大小相等，可以有多维形式，通过整型索引值访问元素，数组尺寸不能改变。

知识点

• 数组的优点：存取速度快。
• 数组的缺点：
  • 事先必须知道数组的长度；
  • 插入删除元素很慢、效率很低；
  • 空间通常是有限制的，需要大块连续的内存块。

JDK 中关于数组的实现，请参考 集合源码 002：ArrayList 源码解析。

数组与矩阵相关题目

把数组中的 0 移到末尾

283. Move Zeroes (Easy)

例如给定 nums = [0, 1, 0, 3, 12]，调用函数之后，nums 应变为 [1, 3, 12, 0, 0]。思路是用一个指针 idx 指向下一个非零元素应存放的位置，遍历一遍把非零元素前移，最后把尾部填 0：

public void moveZeroes(int[] nums) {
    int idx = 0;
    for (int num : nums) {
        if (num != 0) {
            nums[idx++] = num;
        }
    }
    while (idx < nums.length) {
        nums[idx++] = 0;
    }
}

改变矩阵维度

566. Reshape the Matrix (Easy)

将矩阵按行遍历的方式重新排成 r 行 c 列的新矩阵：

Input:
nums = [[1,2],
        [3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix.

原文此处配有矩阵重排示意图（已丢失，据题意重绘）：

flowchart LR
    subgraph before["原矩阵 2×2"]
        direction TB
        r1["1  2"]
        r2["3  4"]
    end
    subgraph after["重排后 1×4"]
        n1["1  2  3  4"]
    end
    before -- "按行遍历 1→2→3→4" --> after

实现时先校验元素总数是否一致，再借助一个递增的 index 将旧矩阵元素映射到新矩阵：

public int[][] matrixReshape(int[][] nums, int r, int c) {
    int m = nums.length, n = nums[0].length;
    if (m * n != r * c) {
        return nums;
    }
    int[][] reshapedNums = new int[r][c];
    int index = 0;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            reshapedNums[i][j] = nums[index / n][index % n];
            index++;
        }
    }
    return reshapedNums;
}

找出数组中最长的连续 1

485. Max Consecutive Ones (Easy)

遍历数组，遇到 1 计数器加一，遇到 0 计数器清零，记录计数器的最大值即可：

public int findMaxConsecutiveOnes(int[] nums) {
    int max = 0, cur = 0;
    for (int x : nums) {
        cur = x == 0 ? 0 : cur + 1;
        max = Math.max(max, cur);
    }
    return max;
}

有序矩阵查找

240. Search a 2D Matrix II (Medium)

矩阵每行从左到右、每列从上到下都是有序的，例如：

[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]

从矩阵的右上角（或左下角）开始查找：目标值比当前元素小则向左移，比当前元素大则向下移，每次排除一行或一列：

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int m = matrix.length, n = matrix[0].length;
    int row = 0, col = n - 1;
    while (row < m && col >= 0) {
        if (target == matrix[row][col]) return true;
        else if (target < matrix[row][col]) col--;
        else row++;
    }
    return false;
}

有序矩阵的 Kth Element

378. Kth Smallest Element in a Sorted Matrix (Medium)

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.

解题参考: Share my thoughts and Clean Java Code。

二分查找解法：对值域而非下标做二分，统计矩阵中小于等于 mid 的元素个数，逐步逼近第 k 小的值：

public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length, n = matrix[0].length;
    int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n && matrix[i][j] <= mid; j++) {
                cnt++;
            }
        }
        if (cnt < k) lo = mid + 1;
        else hi = mid - 1;
    }
    return lo;
}

堆解法：把每行第一个元素放入小根堆，弹出 k - 1 个堆顶元素（每次弹出后将其同行的下一个元素入堆），此时堆顶元素就是第 k 小的：

public int kthSmallest(int[][] matrix, int k) {
    int m = matrix.length, n = matrix[0].length;
    PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
    for(int j = 0; j < n; j++) pq.offer(new Tuple(0, j, matrix[0][j]));
    for(int i = 0; i < k - 1; i++) { // 小根堆，去掉 k - 1 个堆顶元素，此时堆顶元素就是第 k
        Tuple t = pq.poll();
        if(t.x == m - 1) continue;
        pq.offer(new Tuple(t.x + 1, t.y, matrix[t.x + 1][t.y]));
    }
    return pq.poll().val;
}

class Tuple implements Comparable<Tuple> {
    int x, y, val;
    public Tuple(int x, int y, int val) {
        this.x = x; this.y = y; this.val = val;
    }
    @Override
    public int compareTo(Tuple that) {
        return this.val - that.val;
    }
}

堆的原理与 Java 中 PriorityQueue 的实现可参考 集合源码 005：PriorityQueue 源码解析。

找出重复的数和丢失的数

645. Set Mismatch (Easy)

一个数组元素在 [1, n] 之间，其中一个数被替换为另一个数，找出重复的数和丢失的数。

Input: nums = [1,2,2,4]
Output: [2,3]

最直接的方法是先对数组进行排序，这种方法时间复杂度为 O(NlogN)。本题可以以 O(N) 的时间复杂度、O(1) 空间复杂度来求解，主要思想是通过交换数组元素，使得数组上的元素在正确的位置上：

public int[] findErrorNums(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        while (nums[i] != i + 1 && nums[nums[i] - 1] != nums[i]) {
            swap(nums, i, nums[i] - 1);
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return new int[]{nums[i], i + 1};
        }
    }
    return null;
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

类似题目：

• 448. Find All Numbers Disappeared in an Array (Easy)，寻找所有丢失的元素；
• 442. Find All Duplicates in an Array (Medium)，寻找所有重复的元素。

找出数组中重复的数

287. Find the Duplicate Number (Medium)

数组值在 [1, n] 之间，要求不能修改数组，也不能使用额外的空间。

二分查找解法：对 1~n 的值域做二分，统计数组中小于等于 mid 的元素个数，个数大于 mid 说明重复数在左半区间：

public int findDuplicate(int[] nums) {
    int l = 1, h = nums.length - 1;
    while (l <= h) {
        int mid = l + (h - l) / 2;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) cnt++;
        }
        if (cnt > mid) h = mid - 1;
        else l = mid + 1;
    }
    return l;
}

双指针解法：类似于有环链表中找出环的入口，把 nums[i] 看作”下一个节点”的指针，使用快慢指针即可（链表相关内容参考 算法 003：线性表：链表）：

public int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    fast = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}

数组相邻差值的个数

667. Beautiful Arrangement II (Medium)

题目描述：数组元素为 1~n 的整数，要求构建数组，使得相邻元素的差值不相同的个数为 k。

让前 k+1 个元素构建出 k 个不相同的差值，序列为: 1, k+1, 2, k, 3, k-1, ... , k/2, k/2+1。

Input: n = 3, k = 2
Output: [1, 3, 2]
Explanation: The [1, 3, 2] has three different positive integers ranging from 1 to 3,
and the two differences between adjacent integers are 2 and 1, i.e. the number of
different differences is k = 2.

public int[] constructArray(int n, int k) {
    int[] ret = new int[n];
    ret[0] = 1;
    for (int i = 1, interval = k; i <= k; i++, interval--) {
        ret[i] = i % 2 == 1 ? ret[i - 1] + interval : ret[i - 1] - interval;
    }
    for (int i = k + 1; i < n; i++) {
        ret[i] = i + 1;
    }
    return ret;
}

数组的度

697. Degree of an Array (Easy)

题目描述：数组的度定义为元素出现的最高频率，例如数组 [1,2,2,3,1,4,2] 的度为 3（元素 2 出现 3 次）。要求找到一个最小的子数组，这个子数组的度和原数组一样。

Input: [1,2,2,3,1,4,2]
Output: 6

用三个 HashMap 分别记录每个元素的出现次数、首次出现下标和最后一次出现下标，度为最大出现次数，答案取达到该度的元素中”最后下标 - 首次下标 + 1”的最小值：

public int findShortestSubArray(int[] nums) {
    Map<Integer, Integer> numsCnt = new HashMap<>();
    Map<Integer, Integer> numsLastIndex = new HashMap<>();
    Map<Integer, Integer> numsFirstIndex = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        numsCnt.put(num, numsCnt.getOrDefault(num, 0) + 1);
        numsLastIndex.put(num, i);
        if (!numsFirstIndex.containsKey(num)) {
            numsFirstIndex.put(num, i);
        }
    }
    int maxCnt = 0;
    for (int num : nums) {
        maxCnt = Math.max(maxCnt, numsCnt.get(num));
    }
    int ret = nums.length;
    for (int i = 0; i < nums.length; i++) {
        int num = nums[i];
        int cnt = numsCnt.get(num);
        if (cnt != maxCnt) continue;
        ret = Math.min(ret, numsLastIndex.get(num) - numsFirstIndex.get(num) + 1);
    }
    return ret;
}

HashMap 的原理与源码实现可参考 集合源码 006：HashMap 源码解析，哈希表作为数据结构的介绍参考 算法 005：散列表：哈希表。

对角元素相等的矩阵

766. Toeplitz Matrix (Easy)

判断矩阵是否为 Toeplitz 矩阵：每条从左上到右下的对角线上的元素全部相同，例如对角线 [9]、[5, 5]、[1, 1, 1]、[2, 2, 2]、[3, 3] 等。分别从第一行和第一列的每个元素出发，沿对角线递归校验：

public boolean isToeplitzMatrix(int[][] matrix) {
    for (int i = 0; i < matrix[0].length; i++) {
        if (!check(matrix, matrix[0][i], 0, i)) {
            return false;
        }
    }
    for (int i = 0; i < matrix.length; i++) {
        if (!check(matrix, matrix[i][0], i, 0)) {
            return false;
        }
    }
    return true;
}

private boolean check(int[][] matrix, int expectValue, int row, int col) {
    if (row >= matrix.length || col >= matrix[0].length) {
        return true;
    }
    if (matrix[row][col] != expectValue) {
        return false;
    }
    return check(matrix, expectValue, row + 1, col + 1);
}

嵌套数组

565. Array Nesting (Medium)

题目描述：S[i] 表示一个集合，集合的第一个元素是 A[i]，第二个元素是 A[A[i]]，如此嵌套下去，求最大的 S[i]。

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0]=5, A[1]=4, A[2]=0, A[3]=3, A[4]=1, A[5]=6, A[6]=2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}

访问过的位置标记为 -1，避免重复访问，整个算法是线性时间复杂度：

public int arrayNesting(int[] nums) {
    int max = 0;
    for (int i = 0; i < nums.length; i++) {
        int cnt = 0;
        for (int j = i; nums[j] != -1; ) {
            cnt++;
            int t = nums[j];
            nums[j] = -1; // 标记该位置已经被访问
            j = t;
        }
        max = Math.max(max, cnt);
    }
    return max;
}

分隔数组

769. Max Chunks To Make Sorted (Medium)

题目描述：分隔数组，使得对每部分排序后数组就为有序。

Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.

遍历时维护当前分段的最大值 right，当 right == i 说明前 i 个元素恰好组成一个可独立排序的分段：

public int maxChunksToSorted(int[] arr) {
    if (arr == null) return 0;
    int ret = 0;
    int right = arr[0];
    for (int i = 0; i < arr.length; i++) {
        right = Math.max(right, arr[i]);
        if (right == i) ret++;
    }
    return ret;
}

题目与解法复杂度小结

题目	解法思路	时间复杂度	空间复杂度
283. 移动零	双指针，非零前移	O(N)	O(1)
566. 矩阵重排	下标映射 index / n、index % n	O(r * c)	O(r * c)
485. 最长连续 1	计数器遇 0 清零	O(N)	O(1)
240. 有序矩阵查找	右上角出发排除行列	O(m + n)	O(1)
378. 有序矩阵第 k 小	值域二分 / 小根堆	O(n·log(max−min)) / O(k·logN)	O(1) / O(N)
645. 重复与丢失	交换元素归位	O(N)	O(1)
287. 找重复数	值域二分 / 快慢指针	O(NlogN) / O(N)	O(1)
667. 相邻差值个数	前 k+1 个元素交错构造	O(N)	O(1)
697. 数组的度	计数 + 首尾下标	O(N)	O(N)
766. Toeplitz 矩阵	沿对角线递归校验	O(m * n)	O(m + n)
565. 嵌套数组	访问标记 -1	O(N)	O(1)
769. 分隔数组	维护前缀最大值	O(N)	O(1)

系列导航

• 上一篇：数据结构基础知识体系详解
• 下一篇：线性表：链表
• 相关篇：线性表：栈和队列、散列表：哈希表、ArrayList 源码解析