牛客网刷题 | BC123 有序序列插入一个整数

目前主要分为三个专栏，后续还会添加：

        专栏如下：                 C语言刷题解析       C语言系列文章       我的成长经历

感谢阅读！

初来乍到，如有错误请指出，感谢！

描述

有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，保证插入新数后，序列仍然是升序。

输入描述：

第一行输入一个整数N(0≤N≤50)。

第二行输入N个升序排列的整数，输入用空格分隔的N个整数。

第三行输入想要进行插入的一个整数。

输出描述：

输出为一行，N+1个有序排列的整数。

思路： 

1. 读取输入：

   • 首先读取整数 N，表示已有序列中的元素数量。
   • 如果 N 为 0，则直接读取新数字并输出，因为此时序列为空，新数字就是唯一的元素。
   • 否则，读取接下来的 N 个整数构成有序序列。
   • 最后，读取要插入的新数字。

2. 处理边界情况：

   • 如果 N 为 0，直接输出新数字即可。这是最简单的情况。

3. 查找插入位置：

   • 初始化一个索引变量 index 为 0。
   • 使用 while 循环遍历序列，找到第一个大于新数字的位置 index。

     5
     1 3 5 7 9
     6

   • 这个循环会在 sequence[index] > new_number 时停止，或者当 index 达到 N 时停止（即新数字比所有现有元素都大）。

4. 插入新数字：

   • 创建一个新的数组 new_sequence，其长度为 N + 1。
   • 将原序列中小于等于新数字的部分复制到 new_sequence 中。
   • 在 index 位置插入新数字。
   • 将原序列中剩余部分复制到 new_sequence 中。

5. 输出结果：

   • 遍历 new_sequence 数组并输出每个元素，形成新的有序序列。

示例运行

假设输入如下：

5
1 3 5 7 9
6

程序的执行过程如下：

1. 读取输入：

   • 读取 N = 5。
   • 读取有序序列 [1, 3, 5, 7, 9]。
   • 读取新数字 6。

2. 处理边界情况：

   • 因为 N 不为 0，继续执行后续步骤。

3. 查找插入位置：

   • 初始化 index = 0。
   • 开始循环：
     • index = 0，sequence[0] = 1，1 <= 6，index++ → index = 1。
     • index = 1，sequence[1] = 3，3 <= 6，index++ → index = 2。
     • index = 2，sequence[2] = 5，5 <= 6，index++ → index = 3。
     • index = 3，sequence[3] = 7，7 > 6，停止循环。
   • 最终 index = 3。

4. 插入新数字：

   • 创建一个新的数组 new_sequence，长度为 6。
   • 将原序列中小于等于 6 的部分复制到 new_sequence：
     • new_sequence[0] = sequence[0] = 1。
     • new_sequence[1] = sequence[1] = 3。
     • new_sequence[2] = sequence[2] = 5。
   • 在 index = 3 位置插入新数字 6：
     • new_sequence[3] = 6。
   • 将原序列中剩余部分复制到 new_sequence：
     • new_sequence[4] = sequence[3] = 7。
     • new_sequence[5] = sequence[4] = 9。
   • 最终 new_sequence 为 [1, 3, 5, 6, 7, 9]。

5. 输出结果：

   • 遍历 new_sequence 并输出每个元素：
     • printf("1 ")。
     • printf("3 ")。
     • printf("5 ")。
     • printf("6 ")。
     • printf("7 ")。
     • printf("9 ")。
   • 最后换行 printf("\n")。

#include <stdio.h>

int main() {
    int N;
    // 读取整数 N，表示已有序列中的元素数量
    scanf("%d", &N);
    
    // 处理边界情况：如果 N 为 0
    if (N == 0) {
        int new_number;
        // 直接读取新数字
        scanf("%d", &new_number);
        // 输出新数字
        printf("%d\n", new_number);
        // 结束程序
        return 0;
    }
    
    int sequence[N];
    // 读取 N 个整数构成有序序列
    for (int i = 0; i < N; i++) {
        scanf("%d", &sequence[i]);
    }
    
    int new_number;
    // 读取要插入的新数字
    scanf("%d", &new_number);
    
    // 查找插入位置
    int index = 0;
    // 找到第一个大于新数字的位置
    while (index < N && sequence[index] <= new_number) {
        index++;
    }
    
    // 插入新数字
    int new_sequence[N + 1];  // 创建一个新的数组，长度为 N + 1
    // 将原序列中小于等于新数字的部分复制过去
    for (int i = 0; i < index; i++) {
        new_sequence[i] = sequence[i];
    }
    // 在 index 位置插入新数字
    new_sequence[index] = new_number;
    // 将原序列中剩余部分复制过来
    for (int i = index; i < N; i++) {
        new_sequence[i + 1] = sequence[i];
    }
    
    // 输出结果
    // 遍历 new_sequence 数组并输出每个元素，形成新的有序序列
    for (int i = 0; i < N + 1; i++) {
        printf("%d ", new_sequence[i]);
    }
    // 换行
    printf("\n");
    
    // 结束程序
    return 0;
}

代码 2：

#include <stdio.h>

int main() 
{
    int N, i, newNumber;
    int arr[51]; // 声明一个足够大的数组来存储输入的数字

    // 读取第一个整数N
    scanf("%d", &N);

    // 读取N个升序排列的整数
    for (i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    // 读取想要插入的新整数
    scanf("%d", &newNumber);

    // 找到新数应该插入的位置
    int insertIndex = N;
    for (i = 0; i < N; i++) {
        if (arr[i] > newNumber) {
            insertIndex = i;
            break;
        }
    }

    // 将新数插入到找到的位置，并将后续元素后移
    for (i = N; i > insertIndex; i--) {
        arr[i] = arr[i - 1];
    }
    arr[insertIndex] = newNumber;

    // 输出排序后的数组内容
    for (i = 0; i <= N; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}