3.4 特殊位置的插入

“有时候，”我解释道，”我们需要在数组的特殊位置插入元素，比如在最大值的后面插入一个新元素。”

3.4.1 在最大数后面插入一个数

题目描述： 在一个不重复数组的最大数的后面插入一个新的数 y。

输入格式：

• 第一行有一个整数 n ( 5≤n≤100 ）
• 第二行有 n 个整数
• 第三行有一个整数 y，为要插入的数

输出格式： 更新后的数组。

样例输入：

5
7 2 3 4 5
9

样例输出：

7 9 2 3 4 5

代码实现：

#include <iostream>
#include <climits>    // 引入INT_MIN
using namespace std;

int main() {
    int a[110];    // 定义数组，预留足够空间
    int n;         // 数组长度
    cin >> n;
    
    int max_val = INT_MIN;    // 初始化最大值为最小整数
    int max_pos = 0;          // 最大值的位置
    
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] > max_val) {
            max_val = a[i];    // 更新最大值
            max_pos = i;       // 更新最大值的位置
        }
    }
    
    int y;    // 要插入的数
    cin >> y;
    
    // 方法一：直接在输出时插入
    for(int i = 1; i <= n; i++) {
        cout << a[i] << " ";    // 先输出原有元素
        if(i == max_pos) {
            cout << y << " ";    // 在最大值后面输出新值
        }
    }
    
    /*
    // 方法二：移动元素后插入
    for(int i = n; i > max_pos; i--) {
        a[i+1] = a[i];    // 将最大值后面的元素向后移动一位
    }
    a[max_pos+1] = y;     // 在最大值后面插入新值
    
    for(int i = 1; i <= n+1; i++) {
        cout << a[i] << " ";    // 输出n+1个元素
    }
    */
    
    return 0;
}

算法解析：

方法一：

1. 首先找出数组中的最大值及其位置
2. 在输出时，每当输出一个元素后，检查是否是最大值
3. 如果是最大值，则在其后输出新值

方法二：

1. 首先找出数组中的最大值及其位置
2. 从数组末尾开始向前遍历，将最大值后面的元素向后移动一位
3. 在最大值后面的位置插入新值
4. 输出包含新元素的数组（长度增加了1）