解题思路

题目要求在数组的第 x 个位置插入一个新的数 y，插入后数组多一个数。

思路：

1. 先读入原数组
2. 把插入位置从 1 开头的编号转成从 0 开头（x--）
3. 关键：从后往前把 x 位置及以后的元素往后移一格，腾出 x 位置
4. 在 x 位置放入 y
5. 输出插入后的数组

为什么必须从后往前移动？ 如果从前往后移，会把还没移动的元素覆盖掉。从后往前移，每个元素先移走再被覆盖，不会丢数据。

举例：数组 7 2 3 4 5，在位置 2 插入 9：

• 位置转 0 开头：第 2 个位置是下标 1
• 从后往前移动：5→位置4，4→位置3，3→位置2，2→位置1，空出位置1
• 位置1 放入 9：7 9 2 3 4 5

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n + 1];

    for (int i = 0; i < n; i++) cin >> a[i];

    int x, y;
    cin >> x;
    x--;  // 位置从 1 开头转成 0 开头
    cin >> y;

    // 从后往前移动元素，腾出位置
    for (int i = n - 1; i >= x; i--) {
        a[i + 1] = a[i];
    }

    a[x] = y;  // 插入新数

    for (int i = 0; i < n + 1; i++) {
        cout << a[i] << " ";
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，从后往前移动一遍
• 空间复杂度：O(N)，数组多开一个位置