Just for Life.

明月更几时

0%

算法系列：数组类题目

发表于 更新于
本文字数： 11k 阅读时长 ≈ 10 分钟

之前没有很留意，没想到大一学过的数组也能有很多精彩的算法题。本文收录了数组类算法常见的：前缀和、差分数组、常数时间查找和删除数组元素和数组去重问题。

  • 前缀和数组：用于频繁求解给定区间内，数组元素的和
  • 差分数组：用于频繁更改给定区间内数组元素的取值，最后得到数组

前面两个侧重频繁修改数组，常规模拟算法必然超时。而至于常数时间内查找和删除数组元素，数组元素去重已经是固定要求的题目了，文末直接给出题解。

前缀和

前缀和就是输入数组的累计和：

1
2
3
presum[0] = arr[0];
for (int i = 1; i < n; i++)
    presum[i] = presum[i-1] + sum[i];

因此， presum[r] - presum[l-1] 就是数组在区间 [l,r] 内的和。

前缀和算法一般用于求解以下问题：需要频繁的调用某个方法，这个方法需要求出数组在给定区间中元素的和。如果每次查询都要遍历数组求和，会超时的很严重，因此需要使用前缀和来解决。但是众所周知算法不可能这么简单，一边看题一边看前缀和的细节。

303. 区域和检索 - 数组不可变

给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和 ，其中 left <= right。实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 。示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

这个是典型的求解区间数组和的题目，如果每次都暴力计算会超时。因此我们使用前缀和数组来解决问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumArray {
public:

    vector<int> presum;
    NumArray(vector<int>& nums) {
        presum.resize(nums.size());
        presum.assign(nums.size(), 0);
        // 构建前缀和
        presum[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            presum[i] = presum[i-1] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        if (left == 0)
            return presum[right];
        return presum[right] - presum[left - 1];
    }
};

一般不建议这么写，因为 left-1 很容易越界，涉及到二维数组十分不好处理。因此，推荐的写法是，前缀和数组比输入数组大一个维度。此时，只需要让 right+1 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
public:

    vector<int> presum;
    NumArray(vector<int>& nums) {
        presum.resize(nums.size() + 1);
        presum.assign(nums.size() + 1, 0);
        // 前缀和数组
        for (int i = 1; i <= nums.size(); i++) {
            presum[i] = presum[i-1] + nums[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        return presum[right + 1] - presum[left];
    }
};

二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：计算其子矩形范围内元素的总和，该子矩阵的 左上角为 (row1, col1) ，右下角为 (row2, col2) 。实现 NumMatrix 类：

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

对于二维数组，方法还是和一维数组一样，我们求某个坐标对应的前缀和就可以了。但是迫切建议前缀和数组大一个维度，不然边界情况真的很难处理。和一维数组一样，构建数组的前缀和数组，在求解指定区间的数组和时，也是两个边界相减就行，但是有一点点细节要处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class NumMatrix {
public:
    vector<vector<int>> presum;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        presum.resize(m + 1);
        for (int i = 0; i <= m; i++) {
            presum[i].assign(n + 1, 0);
        }
        presum[0][0] = matrix[0][0];
        // 构建二维前缀和数组
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                presum[i][j] = matrix[i-1][j-1] + presum[i-1][j] + presum[i][j-1] - presum[i-1][j-1];
            }
        }
    }
    // 区间相减，但是要注意 presum[row1][col1] 减了两次
    int sumRegion(int row1, int col1, int row2, int col2) {
        return presum[row2+1][col2+1] - presum[row1][col2+1] - presum[row2+1][col1] + presum[row1][col1];
    }
};

1124. 表现良好的最长时间段

这个是和单调栈的梦幻联动，掌握了这个题，前缀和学的就可以了。

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格大于「不劳累的天数」。请你返回「表现良好时间段」的最大长度。示例 1：

1
2
3
输入：hours = [9,9,6,0,6,6,9]
输出：3
解释：最长的表现良好时间段是 [9,9,6]。

一开始的时候毫无头绪，甚至暴力模拟也没有什么太好的思路，直到看了题解。

  1. 因为工作时长以 8 小时为划分，不管是 10 小时还是 13 小时，本质是一样的，7 小时和 8 小时的本质也是一样的。因此，我们新建一个数组 score，大于 8 为 1，否则为 -1。
  2. 根据 score 构建前缀和数组，前缀和数组元素的值越大，表示近期的工作表现越良好。换一种说法，如果 score 数组呈现了上升的趋势，那么说明今天在好好工作。
  3. 因此，我们只需要求前缀和数组中的最大上升跨度，就是劳累天数严格大于不劳累天数，结果即为表现良好的时间段。最大跨度请参考单调栈那篇文章的最后一题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int longestWPI(vector<int>& hours) {
        int n = hours.size();
        vector<int> presum(n + 1, 0);
        vector<int> socre(n, 0);
        for (int i = 0; i < n; i++) {
            socre[i] = hours[i] > 8 ? 1 : -1;
        }
        // 前缀和
        for (int i = 1; i <= n; i++) {
            presum[i] = presum[i-1] + socre[i-1];
        }
        // 单调递减栈
        stack<int> stk;
        for (int i = 0; i < n + 1; i++) {
            if (stk.empty() || presum[stk.top()] > presum[i]) {
                stk.push(i);
            }
        }
        // 最大上升跨度
        int ans = 0;
        for (int i = n; i >= 0; i--) {
            while (stk.size() && presum[stk.top()] < presum[i]) {
                ans = max(ans, i - stk.top());
                stk.pop();
            }
        }
        return ans;
    }
};

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减，然后问你修改后的数组是多少。差分数组的构造方式为：

1
2
3
4
diff[0] = arr[0];
for (int i = 1; i < n; i++) {
    diff[i] = arr[i] - arr[i-1];
}

如果让数组区间 [l, r] 内的元素增加 3，只需要让 diff[l]+3, diff[r]-3 即可 （自己画图理解下）。而通过 diff 也能得到原始的数组：

1
2
3
4
arr[0] = diff[0];
for (int i = 1; i < n; i++) {
    arr[i] = arr[i-1] + diff[i];
}

1109. 航班预订统计

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [first[i], last[i], seats[i]] 意味着在从 first[i] 到 last[i] （包含 first[i] 和 last[i] ）的每个航班上预订了 seats[i] 个座位。请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。示例 1：

1
2
3
4
5
6
7
8
9
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

典型的差分数组应用：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> diff(n, 0);
        for (auto i : bookings) {
            int s = i[0] - 1;
            int e = i[1] - 1;
            int v = i[2];
            diff[s] += v;
            // 防止越界
            if (e + 1 <= n - 1)
                diff[e + 1] -= v;
        }
        vector<int> res(n, 0);
        res[0] = diff[0];
        for (int i = 1; i < n; i++) {
            res[i] = res[i-1] + diff[i];
        }
        return res ;
    }
};

拼车

车上最初有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向。给定整数 capacity 和一个数组 trips , trip[i] = [numPassengers[i], from[i], to[i]] 表示第 i 次旅行有 numPassengers[i] 乘客，接他们和放他们的位置分别是 from[i] 和 to[i] 。这些位置是从汽车的初始位置向东的公里数。当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。示例 1：

1
2
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

这里需要注意的是，比如客户 A 在 5 下车，而客户 B 在 5 上车，此时是能顺利交接的。因此，下车的时候，diff[r]-n 即可，不需要占用 r 处的容量。可以理解为，在地点 4 ，车上就没有客户了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> diff(1005, 0);
        for (auto i : trips) {
            int v = i[0];
            int s = i[1];
            int e = i[2];
            diff[s] += v;
            diff[e] -= v;
        }
        vector<int> res(1005, 0);
        res[0] = diff[0];
        // 细节判断
        if (res[0] > capacity)
            return false;
        for (int i = 1; i < 1005; i++) {
            res[i] = res[i-1] + diff[i];
            if (res[i] > capacity)
                return false;
        }
        return true;
    }
};

数组去重

给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。示例：

1
2
输入：s = "bcabc"
输出："abc"

严格来说，这算一个模拟题，只要思路足够清晰，是可以写出代码的：

  1. 每个字符只出现一次，因此在遍历字符串时，如果当前字符已经被添加到结果中时，需要跳过当前字符，避免重复；
  2. 如果当前字符没有在结果中，添加当前字符时需要一些处理来满足字典序。如果这个字符比上一个字符的字典序小，且上一个字符后面还会出现，我们就需要弹出上一个字符，添加当前字符。

如果要实现以上两点，就需要使用哈希和栈。need 哈希表用于记录每个字符出现的次数，每添加一次，取值就递减，可以判断这个字符之后还会不会出现，以及出现的次数。isin 哈希表判断当前字符是否已经添加。res 栈用来存储结果，因为栈可以方便的弹出末尾元素来使字典序更小。程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char, int> need;
        // 记录次数
        for (int i = 0 ; i < s.size(); i++) {
            need[s[i]] ++;
        }
        stack<char> res;
        vector<bool> isin(26, false);
        for (auto i : s) {
            // 之后出现的次数递减
            need[i]--;
            // 不在结果中
            if (isin[i - 'a'] == false) {
                // 可以弹栈的情况
                while (res.size() && need[res.top()] > 0 && res.top() > i) {
                    auto a = res.top();
                    res.pop();
                    // 弹栈后不在结果中
                    isin[a - 'a'] = false;
                }
                res.push(i);
                isin[i - 'a'] = true;
            }
        }
        string ans{""};
        while (res.size()) {
            ans += res.top();
            res.pop();
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

$O(1)$ 时间查找和删除元素

刚开始看到题的时候给我整不会了，众所周知数组内查找元素的时间复杂度为 $O(n)$，有序数组内查找元素的时间复杂度为 $O(\log n)$，怎么可能做到 $O(1)$。

但看到题目是这种类的时间，频繁的调用方法插入和删除，那么 $O(1)$ 时间的查找和删除也有了可能。只需要在插入的时候通过哈希记录数值的索引，那么能很轻松的查找到数值是否在数组中，以及它的索引。

而要实现 $O(1)$ 的删除元素，我们知道 C++ 的 STL 支持 $O(1)$ 删除的只有 pop_back() 这样的方法。因此，当需要删除某一个值时，我们把这个数值和数组末尾的数值进行交换，而后 pop_back() 即可。

实现 RandomizedSet 类：

  1. RandomizedSet() 初始化 RandomizedSet 对象
  2. bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
  3. bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
  4. int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
    你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class RandomizedSet {
public:

    unordered_map<int, int> m1;
    vector<int> arr;

    RandomizedSet() {

    }
    // 插入时记录索引
    bool insert(int val) {
        if (m1.count(val)) {
            return false;
        }
        arr.push_back(val);
        m1[val] = arr.size() - 1;
        return true;
    }

    bool remove(int val) {
        if (!m1.count(val)) {
            return false;
        }
        int val_idx = m1[val];
        int back_val = arr.back();
        int back_idx = m1[back_val];
        // 和末尾元素交换
        arr[val_idx] = back_val;
        m1[back_val] = val_idx;
        m1.erase(val);
        arr.pop_back();
        return true;
    }
    // 随机选择
    int getRandom() {
        int idx = rand() % arr.size();
        return arr[idx];
    }
};

寻找数组重复和缺失元素

直接来看题目吧。

645. 错误的集合

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合丢失了一个数字并且有一个数字重复。给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。示例：

1
2
输入：nums = [1,2,2,4]
输出：[2,3]

对于如上的示例，正常的数组应该是 [1,2,3,4]，因此，重复的是 2，缺失的是 3。其实这个题挺简单的，没啥可说的，面试碰到这个题可以内心狂喜了。即使不看题解，绝大多数人也知道怎么去做。再不济输入数组排序，然后依次遍历，总能查到重复的和缺失的。

但是排序的时间复杂度可能有点高，我们优化一下这个复杂度。创建一个哈希数组：

  1. 首先遍历原数组得到数值，以数值为索引，反哈希数组中的值设置为 true
  2. 这样，在下一次遇到 true 时，就能得到重复元素
  3. 遍历哈希数组，如果元素为 false，说明索引对应的值为缺失值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> arr(nums.size(), 1);
        for (int i = 1; i <= nums.size(); i++) {
            arr[i-1] = i;
        }
        int a, b;
        for (auto i : nums) {
            if (arr[i-1] != -1) {
                arr[i-1] = -1;
            } else {
                a = i;
            }
        }
        for (auto i : arr) {
            if (i != -1) {
                b = i;
            }
        }
        return {a, b};
    }
};

接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

注：华为2022提前批类似题目。柱子能接多少雨水，完全取决于左侧的最高高度和右侧的最高高度，我们可以得到每个柱子的左侧最高和右侧最高，那么所能存储的雨水就是：左侧最高的和右侧最高的中的最小值，减去当前柱子的高度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> l_max(n, 0);
        vector<int> r_max(n, 0);
        l_max[0] = height[0];
        r_max[n-1] = height.back();
        
        for (int i = 1; i < n; i++) {
            l_max[i] = max(l_max[i-1], height[i]);
        }
        for (int i = n-2; i >= 0; i--) {
            r_max[i] = max(r_max[i+1], height[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(l_max[i], r_max[i]) - height[i];
        }
        return ans;
    }
};
本文相关
感谢上学期间打赏我的朋友们。赛博乞讨：我，秦始皇，打钱。

欢迎订阅我的文章