蓝桥杯备赛——“双指针”“三指针”解决vector相关问题

一、寄包柜

相关代码：

#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, q;
vector<int> a[N]; // 创建 N 个柜⼦ 
int main()
{cin >> n >> q;while(q--){int op, i, j, k;cin >> op >> i >> j;if(op == 1) // 存 {cin >> k;if(a[i].size() <= j){// 扩容 a[i].resize(j + 1);}a[i][j] = k;}else // 查询 {cout << a[i][j] << endl;}}return 0;
}

代码解读：

• const int N = 1e5 + 10;：定义一个常量 N，其值为 100000 + 10，用于表示柜子的最大数量。
• int n, q;：定义两个整数变量 n 和 q，n 未在代码中使用，q 表示操作的次数。
• vector<int> a[N];：创建一个包含 N 个 vector<int> 对象的数组 a，每个 vector<int> 可以看作一个柜子，用于存储整数。

int main()
{cin >> n >> q;while(q--){int op, i, j, k;cin >> op >> i >> j;if(op == 1) // 存 {cin >> k;if(a[i].size() <= j){// 扩容 a[i].resize(j + 1);}a[i][j] = k;}else // 查询 {cout << a[i][j] << endl;}}return 0;
}

• cin >> n >> q;：从标准输入读取两个整数 n 和 q，分别表示柜子数量（实际未使用）和操作次数。
• while(q--)：循环 q 次，每次处理一个操作。
  • int op, i, j, k;：定义四个整数变量，op 表示操作类型，i 表示柜子编号，j 表示格子编号，k 表示要存入的值。
  • cin >> op >> i >> j;：从标准输入读取操作类型、柜子编号和格子编号。
  • if(op == 1)：如果操作类型为 1，表示存储操作。
    • cin >> k;：从标准输入读取要存入的值 k。
    • if(a[i].size() <= j)：检查当前柜子 a[i] 的大小是否小于等于要存入的格子编号 j。
      • a[i].resize(j + 1);：如果是，则对柜子 a[i] 进行扩容，使其大小至少为 j + 1。
    • a[i][j] = k;：将值 k 存入柜子 a[i] 的第 j 个格子中。
  • else：如果操作类型不为 1，表示查询操作。
    • cout << a[i][j] << endl;：输出柜子 a[i] 的第 j 个格子中存储的值，并换行。

复杂度分析

• 时间复杂度：对于存储操作，如果需要扩容，时间复杂度为 \(O(j)\)，因为 resize 操作可能需要重新分配内存并复制元素；对于查询操作，时间复杂度为 \(O(1)\)。
• 空间复杂度：主要取决于存储的元素数量，最坏情况下为 \(O(N * M)\)，其中 \(N\) 是柜子的数量，\(M\) 是每个柜子中格子的最大数量。

二、移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:

输入: nums = [0]
输出: [0]

提示:

解法：

在本题中，我们可以⽤⼀个 指针来扫描整个数组，另⼀个 指针⽤来记录⾮零数序列的最后
⼀个位置。根据 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
cur dest
cur
在cur 遍历期间，使[0, dest] 的元素全部都是⾮零元素，[dest + 1, cur − 1] 的元素全是零。

如下图：

①当扫描元素是0的时候，我们要想让它出现在中间的区间中，因此我们只需让i++就可以了。

②当扫描元素是非零元素的时候，我们想让它出现在第一个区间中，因此我们要交换当前元素和cur+1所指向的元素，也就是【cur+1】和【i】。交换完之后让cur++，i++。

代码演示：

class Solution 
{
public:void moveZeroes(vector<int>& nums) {for(int i = 0, cur = -1; i < nums.size(); i++){if(nums[i]) // ⾮0元素 {swap(nums[++cur], nums[i]);}}}
};

代码解读：

• 变量初始化：

  • int i = 0：这是一个循环变量，用于遍历向量 nums 中的每个元素，从索引 0 开始。
  • int cur = -1：cur 是一个辅助变量，用于记录当前非零元素应该放置的位置。初始化为 -1，表示还没有遇到非零元素。

• 循环遍历：

  • i < nums.size()：循环条件，确保 i 在向量的有效索引范围内。
  • i++：每次循环结束后，i 自增 1，指向下一个元素。

• 条件判断：

  • if(nums[i])：这是一个条件判断语句，判断当前元素 nums[i] 是否为非零元素。在 C++ 中，非零值被视为 true，零值被视为 false，所以这个条件等价于 if(nums[i] != 0)。

• 交换操作：

  • swap(nums[++cur], nums[i])：如果当前元素 nums[i] 是非零元素，执行以下操作：
    • ++cur：先将 cur 的值加 1，使其指向下一个可以放置非零元素的位置。
    • swap(...)：使用 swap 函数交换 nums[cur] 和 nums[i] 的值。这样，非零元素就会被依次移动到向量的前面，而零元素会被逐渐挤到向量的后面。

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 是向量 nums 的长度。因为代码只对向量进行了一次遍历，每个元素最多被访问和交换一次。
• 空间复杂度：\(O(1)\)，只使用了常数级的额外空间，没有使用与向量长度相关的额外数据结构。

示例调用

#include <iostream>
#include <vector>class Solution 
{
public:void moveZeroes(std::vector<int>& nums) {for(int i = 0, cur = -1; i < nums.size(); i++){if(nums[i]) // ⾮0元素 {std::swap(nums[++cur], nums[i]);}}}
};int main() {std::vector<int> nums = {0, 1, 0, 3, 12};Solution sol;sol.moveZeroes(nums);for (int num : nums) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

在上述示例中，我们创建了一个包含 0 和非零元素的向量 nums，调用 Solution 类的 moveZeroes 函数对其进行处理，最后输出处理后的向量。运行代码后，输出结果将是 1 3 12 0 0，即所有 0 元素都被移动到了向量的末尾，非零元素的相对顺序保持不变。

三、颜色分类

【题⽬描述】
给定⼀个包含红⾊、⽩⾊和蓝⾊、共 个元素的数组 ，原地对它们进⾏排序，使得相同颜
⾊的元素相邻，并按照红⾊、⽩⾊、蓝⾊顺序排列。
n nums
我们使⽤整数0 、1 和2 分别表⽰红⾊、⽩⾊和蓝⾊。
必须在不使⽤库的sort 函数的情况下解决这个问题。
【⽰例⼀】
输⼊：
nums=[2,0,2,1,1,0]
输出：
[0,0,1,1,2,2]

解法
类⽐数组分两块的算法思想，这⾥是将数组分成三块，那么我们可以再添加⼀个指针，实现数组分三块。
设数组⼤⼩为n ，定义三个指针left, cur, right :
• left ：⽤来标记0 序列的末尾，因此初始化为−1 ；• cur ：⽤来扫描数组，初始化为0 ；
• right ：⽤来标记2 序列的起始位置，因此初始化为n 。
在cur 往后扫描的过程中，保证：
• [0, left] 内的元素都是0 ；
• [left + 1, cur − 1] 内的元素都是1 ；
• [cur, right − 1] 内的元素是待定元素；
• [right, n] 内的元素都是2 。

①当扫描到1的时候，我们想把它放到中间第二个区间里面，因此我们可以让i++即可实现。

②当扫描到0的时候，我们想把它放到第一个区间中，因此我们可以让i和left+1进行交换，然后left++，i++。

③当扫描到2的时候，我们想把它放到最后一个区间中，因此我们交换i和right-1，然后right--。但是i得位置是不可以动的。（因为right-1原先是带扫描区域的数，和i交换之后需要再次判断）

代码如下：

class Solution 
{
public:void sortColors(vector<int>& nums) {int n = nums.size();int left = -1, right = n, i = 0;while(i < right){if(nums[i] == 0) swap(nums[++left], nums[i++]);else if(nums[i] == 1) i++;else swap(nums[--right], nums[i]);}}
};

代码解读：

• class Solution：定义了一个名为 Solution 的类，用于封装解决特定问题的方法。
• void sortColors(vector<int>& nums)：定义了一个公共成员函数 sortColors，它接受一个整数向量的引用 nums 作为参数，并且不返回任何值（返回类型为 void）。该函数的目的是对传入的向量进行原地排序。

• int n = nums.size();：获取向量 nums 的长度，方便后续使用。
• int left = -1：left 指针用于标记 0 元素区域的右边界，初始化为 -1，表示初始时 0 元素区域为空。
• int right = n：right 指针用于标记 2 元素区域的左边界，初始化为 n，表示初始时 2 元素区域为空。
• int i = 0：i 是当前正在处理的元素的索引，从数组的第一个元素开始。

• 循环条件：while(i < right)，只要当前处理的元素索引 i 小于 2 元素区域的左边界 right，就继续循环。
• 处理当前元素 nums[i] 的三种情况：
  1. nums[i] == 0：
     • 如果当前元素是 0，将其交换到 0 元素区域的末尾。++left 先将 left 指针右移一位，指向 0 元素区域的下一个位置，然后使用 swap(nums[++left], nums[i++]) 交换 nums[left] 和 nums[i] 的值，并且 i 指针也右移一位，继续处理下一个元素。
  2. nums[i] == 1：
     • 如果当前元素是 1，不需要进行交换，直接将 i 指针右移一位，继续处理下一个元素。因为 1 元素应该位于数组的中部，当前位置就是合适的位置。
  3. nums[i] == 2：
     • 如果当前元素是 2，将其交换到 2 元素区域的开头。--right 先将 right 指针左移一位，指向 2 元素区域的前一个位置，然后使用 swap(nums[--right], nums[i]) 交换 nums[right] 和 nums[i] 的值。注意这里 i 指针不移动，因为交换过来的元素还需要再次判断。

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 是向量 nums 的长度。因为代码只对向量进行了一次遍历，每个元素最多被交换一次。
• 空间复杂度：\(O(1)\)，只使用了常数级的额外空间，没有使用与向量长度相关的额外数据结构。

四、合并两个数组

给你两个按⾮递减顺序排列的整数数组 和 ，另有两个整数 和 ，分别表⽰
和 中的元素数⽬。
nums1 nums2 m n
nums1 nums2
请你合并nums2 到nums1 中，使合并后的数组同样按⾮递减顺序排列。注意：最终，合并后数组不应由函数返回，⽽是存储在数组 中。为了应对这种情况，
的初始⻓度为 ，其中前 个元素表⽰应合并的元素，后 个元素为 ，应忽
略。 的⻓度为 。
nums1
nums1 m + n m n 0
nums2 n
【⽰例⼀】
输⼊：
nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3
输出：
[1,2,2,3,5,6]

解法⼀：利⽤辅助数组（需要学会，归并排序的核⼼步骤）
可以创建⼀个辅助数组，然后⽤两个指针分别指向两个数组。每次拿出⼀个较⼩的元素放在辅助数组中，直到把所有元素全部放在辅助数组中。最后把辅助数组的结果覆盖到nums1 中。

lass Solution 
{
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 解法⼀：利⽤辅助数组 vector<int> tmp(m + n);int cur = 0, cur1 = 0, cur2 = 0;while(cur1 < m && cur2 < n){if(nums1[cur1] <= nums2[cur2]) tmp[cur++] = nums1[cur1++];else tmp[cur++] = nums2[cur2++];}while(cur1 < m) tmp[cur++] = nums1[cur1++];while(cur2 < n) tmp[cur++] = nums2[cur2++];for(int i = 0; i < n + m; i++) nums1[i] = tmp[i];}
};