C++代码入门02：Vector中的push

C++代码入门02：Vector中的push_back

图源：文心一言

上机题目练习整理，本篇作为线性表的代码补充，提供了两种（差别并不大）算法，供小伙伴们参考~🥝🥝

第1版：在力扣新手村刷题的记录
- 方法一：自己写的普通答案，借助辅助容器，循环+赋值；
- 方法二：文心一言老师提供的建议，借助辅助容器，循环+Push_back~🧩🧩

编辑：梅头脑🌸

题目：1470. 重新排列数组 - 力扣（LeetCode）

📇目录

🧵转换小写字母的题目

🧩题目

🌰方法一：常规赋值解法

🌰方法二：使用push_back

🔚结语

🧵转换小写字母的题目

🧩题目

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。

请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。

示例 1：
输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7] 
解释：由于 x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 ，所以答案为 [2,3,5,4,1,7]
示例 2：
输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]
示例 3：
输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]
提示：

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3

🌰方法一：常规赋值解法

📇算法思路

算法思想：将容器视为数组，使用for循环，分别把 x组的元素nums[i] 与 y组的元素nums[n+i] 给到新的数组nums1[2*i]与nums1[2*i+1]；
时间复杂度：O(n)，其中n是数组的长度，代码使用了辅助数组。
空间复杂度：O(n)，其中n是数组的长度，代码中每个元素都被遍历了一遍。

⌨️算法代码

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> nums1(2 * n);   // 初始化nums1的大小为2n
        for (int i = 0; i < n; i++) {
            nums1[2 * i] = nums[i]; // 取x部分的元素
            nums1[2 * i + 1] = nums[n + i]; // 取y部分的元素
        }
        return nums1;
    }
};

⌨️温馨提示

可能问题：请注意，以下写法可能会导致上图的编译错误：

第4行直接写为：“vector<int> nums1;”，而非“vector<int> nums1(2 * n);”

问题所在：nums1 被声明了，但没有被初始化。

在 C++ 中，如果你没有初始化一个 std::vector，它的初始大小将是 0。当你试图访问它的元素时（例如 nums1[2 * i]），将会导致未定义行为，因为你正在访问一个不存在的元素。

🌰方法二：使用push_back

📇算法思路

算法思想：使用push_back方法，依次将分别把 x组的元素nums[i] 与 y组的元素nums[n+i] 添加到新的数组 result 的末端；
时间复杂度：O(n)，其中n是数组的长度。
空间复杂度：O(n)，其中n是数组的长度。

⌨️算法代码

class Solution {  
public:  
    vector<int> shuffle(vector<int>& nums, int n) {  
        vector<int> result; // 创建一个空的result vector  
        // 遍历数组的前半部分（x部分）和后半部分（y部分）  
        for (int i = 0; i < n; i++) {  
            // 依次将x部分的元素和y部分的元素添加到结果vector中  
            result.push_back(nums[i]);          // 添加x部分的元素  
            result.push_back(nums[n + i]);      // 添加y部分的元素  
        }  
        return result; // 返回重新排列后的数组  
    }  
};

⌨️知识扩展

push_back功能

push_back 是 C++ 标准库容器 vector 中的一个成员函数，用于在向量的末尾添加一个元素。当你调用 push_back 方法时，它会做两件事情：

在 vector 的当前末尾之后分配空间来存储一个新元素。
将新元素复制到分配的空间中，并更新 vector 的大小（size）以反映新添加的元素。

这里有一个简单的例子来展示 push_back 的用法：

我们首先创建了一个空的 vector<int> 名为 numbers。
然后，我们使用 push_back 方法三次，每次将一个整数添加到 vector 的末尾。
最后，我们遍历 vector 并输出其内容，结果将是 1 2 3。
#include <iostream>  
#include <vector>  
  
int main() {  
    // 创建一个空的 vector<int>  
    std::vector<int> numbers;  
  
    // 使用 push_back 添加元素到 vector 的末尾  
    numbers.push_back(1);  
    numbers.push_back(2);  
    numbers.push_back(3);  
  
    // 输出 vector 的内容  
    for (int num : numbers) {  
        std::cout << num << " ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

push_back性能

push_back 的内存分配：

当使用push_back向vector添加元素时，如果当前已分配的内存不足以容纳新元素，vector将重新分配更大的内存块，并将现有元素复制到新位置。这个过程可能会导致性能开销，特别是在大量添加元素时。然而，现代C++标准库的实现通常通过智能内存管理策略来减少这种开销，例如使用指数增长策略来分配内存。

push_back 的时间复杂度：通常是摊还常数时间。

换句话说，虽然在最坏情况下，单次push_back的时间复杂度是O(n)，但是在多次操作的平均情况下，由于内存重新分配和元素复制的分摊效果，每个push_back操作的平均时间复杂度可以降低到O(1)。这就是为什么通常说push_back的摊还时间复杂度是O(1)。

相关参考：🌸https://www.cnblogs.com/limaodeng/p/12651835.html

方法一与方法二的比较

适用场景：方法一适用于已知最终元素数量的情况，因为它通过提前分配足够的内存来避免多次内存重新分配。方法二则更适用于元素数量不确定或动态变化的情况，因为它提供了更大的灵活性。
性能差异：在已知元素数量的情况下，方法一通常具有更好的性能，因为它避免了多次内存重新分配和数据复制。然而，在元素数量不确定的情况下，方法二的性能也是可以接受的，尤其是当使用现代C++标准库实现时。