首页 > 试题广场 >

有序序列插入一个数

[编程题]有序序列插入一个数

热度指数：26137 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

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

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

输出描述:

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

示例1

输入

5
1 6 9 22 30
8

输出

1 6 8 9 22 30

算法知识视频讲解

C/C++

金山办公内推官

#include<cstdio>
#include<cstdlib>
/*需要stdlib.h提供malloc函数*/
int main()
{
    int i,n,k;
    int *a;
    scanf("%d",&k);
    a=(int *)malloc(sizeof(int)*(k+1));//根据k的大小来规定数组的大小
    for(i=0;i<k;i++)
        scanf("%d",&a[i]);//输入有序数
    scanf("%d",&n);//输入要插入的数
    for(i=k;a[i-1]>n;i--)
    {
        a[i]=a[i-1];//从后往前寻找并移动数组
    }
    a[i]=n;//找到插入位置后插入
    for(i=0;i<=k;i++)
        printf("%d ",a[i]);
    return 0;
}

编辑于 2020-03-31 17:22:53 回复(0)

C/C++

叶之秋YeQ

C++语言的STL库中的容器Set属于集合类型的容器，该容器满足的特性就是数学中集合的特性。向set集合每插入一个元素，容器会自动对立面的元素进行从小到大排序。从而省去了大量的手动插入和手动排序的时间，最后定义一个迭代器来遍历整个容器内的元素。感兴趣的话可以了解了解STL

#include<bits/stdc++.h>
using namespace std;
int main(){
    set<int> s;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;
        s.insert(num);
    }
    int m;
    cin >> m;
    s.insert(m);
    for(set<int>::iterator it = s.begin(); it != s.end(); it++)
        cout << *it << " ";
    return 0;
}

发表于 2020-06-01 16:03:25 回复(1)

C/C++

字节内推小跟班

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> ans;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        ans.push_back(temp);
    }
    int m;
    cin >> m;
    ans.push_back(m);
    sort(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++)
        printf("%d ", ans[i]);
    return 0;
}

编辑于 2020-04-16 22:26:47 回复(0)

六子的猫猫会后空翻

这道题理论上可以先定义一个 n+1 的数组，先把所有数都接收到，随后再进行排序，但是由于排序的开销更大。所以推荐还是使用数组后移的思路来做。

#include <stdio.h>

int main(void)
{
    int num, n, index;
    scanf("%d", &n);
    int arr[n + 1];
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    scanf("%d", &num);
    n++;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] > num)
        {
            index = i;
            break;
        }
    }
    for (int i = n; i > index; i--)
        arr[i] = arr[i - 1];
    arr[index] = num;
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

发表于 2022-01-09 21:25:07 回复(0)

xiaolock883

这道题的关键在于如何将数组的元素向后进行平移,推荐使用先判断再平移的方法，否则的话需要像我一样，在for循环中添加break，并且循环后需要判断是否最后一个元素都比要添加进去的元素大，如果是这样的话需要将要添加进去的元素直接放到数组的最后一位上去。因此推荐先在for循环中判断，再移动数组。

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n,i,x,j;
    int* p;
    scanf("%d",&n);
    p = (int*)malloc((n+1)*sizeof(int));
    for(i = 0;i<n;i++)
    {
        scanf("%d",&p[i]);
    }
    scanf("%d",&x);
    for(i = 0;i<n;i++)
    {       
        if(x<p[i])
        {
            for(j = n;j>i;j--)
            {
                 p[j] = p[j-1];
            }
            p[i] = x;
            break;
        }
    }
    if(p[n]==0)
    {
            p[i] = x;
    }
    for(i = 0;i<n+1;i++)
    {
        printf("%d ",p[i]);
    }
    free(p);
    p = NULL;
    return 0;
}

发表于 2021-11-18 19:57:20 回复(0)

在敲键盘的coder很幸运

# include <stdio.h>
int main(){
    //输入整数
    int n=0;
    scanf("%d",&n);
    //输入整数数组
    int i=0;
    int arr[51]={0};
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    //输入要插入的数字
    int add=0;
    scanf("%d",&add);
    //插入数字
    for(i=0;i<n;i++){
        if(add < arr[0]){  //要插入的数字比首元素都要小
            int k=0;
            for(k=0;k<n;k++){
                arr[n-(k+1)+1]=arr[n-(k+1)];
            }
            arr[0] = add;
            break;
        }
        if(add > arr[n-1]){ //要插入的数字比尾元素都要大
            arr[n] = add;
            break;
        }
        if( (add>arr[i]&&add<arr[i+1]) ){ //要插入的数字介于两数之间
            int k=0;
            for(k=0;k<(n-(i+1));k++){
                arr[n-(k+1)+1]=arr[n-(k+1)];
            }
            arr[i+1]=add;
            break;
        }
    }
    for(i=0;i<(n+1);i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

发表于 2021-08-29 11:35:26 回复(0)

Java

ningjingjing0614

import java.util.*;

public class Main {
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] arr1 = new int[n];

        String[] str = sc.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(str[i]);
        }
        int m = Integer.parseInt(sc.nextLine());
        int[] arr2 = new int[n + 1];
        for (int i = 0; i < arr1.length; i++) {
            arr2[i] = arr1[i];
        }
        arr2[n] = m;
        Arrays.sort(arr2);
        for (int i = 0; i < arr2.length; i++) {
            System.out.print(arr2[i] + " ");
        }
    }
}

发表于 2021-07-13 20:50:08 回复(0)

QINQING

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
   
    int a[51]={0};
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        
    }
    int x;
    scanf("%d",&x);
    for (int i=0;i<n;i++)
    {
        if(x<=a[i])
        {
            for(int j=n;j>i;j--)
            {
                a[j]=a[j-1];
            }
            a[i]=x;
            break;
        }
        else
        {
            a[n]=x;
        }
        
    }
    for (int w=0;w<n+1;w++)
    {
        printf("%d ",a[w]);
    }
    
}

发表于 2021-01-10 14:50:48 回复(0)

Python

想找到工作的菜鸡

while True:
    try:
        a=int(input())
        b=list(map(int,input().split(" ")))
        #print(b)
        c=int(input())
        b.append(c)
        B=sorted(b)
        print(" ".join(map(str,B)))

    except:
        break

本题有以下几个注意点：

1.使用list来存储数据

2.对于一行多次输入的运用

3.向一个list中添加元素---append()

4.排序sorted()----默认升序

5.list与str的相互转化-------list转化为str：使用.join()函数，同时注意，当列表中元素不为str类型时，需要将元素转化为str类型

发表于 2020-05-26 08:52:36 回复(0)

宇南

为什么我这代码当输入数据

3
1 10 100
88
时输出错误，明明在dvec++上运行结果是正确的，而且在牛客上的调试也是正确结果啊，就很迷惑

#include<stdio.h>

int main()
{
int n,cr,i,j,a;
scanf("%d\n",&n);
int arr1[n],arr2[n+1];
i=0;
while(i<n)
{
scanf("%d",&arr1[i]);
i++;
}
scanf("%d",&cr);
for(i=0;i<n;i++)
{
if(cr>=arr1[i]&&cr<arr1[i+1])
{
j=i+1;
a=i;
arr2[j]=cr;
for(j,i=i+1;j<n+1;j++,i++)
{
arr2[j+1]=arr1[i];
}
for(j=0,i=0;j<=a;j++,i++)
{
arr2[j]=arr1[i];
}
}

}
for(i=0;i<n+1;i++)
{
printf("%d ",arr2[i]);
}
return 0;
}

发表于 2021-08-20 12:22:13 回复(0)

C/C++

热爱前端

#include

int main()
{
int a[55],b[55];//a数组用于输出答案，b数组用于参照
int n=0,i,c,d,e,f,g;//需要用到的变量

scanf("%d",&n);//输入第一行一个整数

//输入第二行的数据，并把a数组的值赋给b数组
for(i=0;i<n;i++)
{
    scanf("%d",&a[i]);
    b[i]=a[i];
}

//输出第三行的数
scanf("%d",&c);
//找到需要改变值的下标
for(d=0;d<n;d++)
{
    if(c<b[d])
    {
        e=d;//需要改变值的下标
        break;//找到后结束for循环
    }
}

a[e]=c;//把插入的值进行插入

//往后移动其他数据
for(f=e+1;f<=n;f++)
{
    a[f]=b[f-1];

}

//输出结果
for(g=0;g<=n;g++)
{
    printf("%d ",a[g]);

}
return 0;

}

编辑于 2020-04-14 10:33:54 回复(0)

喝醉了Ta的梦,晚安

#include<stdio.h>

int main()
{
    int N;
    scanf("%d",&N);
    int arr[100]={0};
    for(int i=0;i<N;i++){
        scanf("%d",&arr[i]);
    }
    int m;
    scanf("%d",&m);
    //输入完毕，现在进行一次插入排序
    int end=N-1;
    while(end>=0){
        if(arr[end]>m){
            arr[end+1]=arr[end];
            end--;
        }
        else{break;}
    }
    arr[end+1] = m;
    for(int i=0;i<=N;i++){
        printf("%d ",arr[i]);
    }
    return 0;
}

发表于 2021-08-28 15:37:51 回复(0)

C/C++

已注销

#include <stdio.h>
#define N 50

int main(void)
{
    int i, j, k, t, n, a[N + 1];
    
    scanf("%d", &n);
    getchar();
    for (i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    getchar();
    scanf("%d", &j);
    for (i = 0; i < n; i++)
    {
        if (j <= a[i])
        {
            for (k = n - 1 ; k >= i; k--)
            {
                a[k + 1] = a[k];//数组向后移动;
            }
            a[i] = j;//放置添加的数;
            break;
        }
    }
    if (i == n)//如果要添加的数比原数组所有元素都大;
    {
        a[i] = j;//就放置到数组末尾;
    }
    for (i = 0; i < n + 1; i++)
    {
        printf("%d ", a[i]);
    }
    
    return 0;
}

编辑于 2020-04-18 18:52:36 回复(0)

阿金要努力

#include<stdio.h>
int main()
{
	int b = 0;
	int c[100] = { 0 };
	scanf("%d", &b);//输入一个数，表示一共有b个数；
	for (int i = 0; i < b; i++)
	{
		scanf("%d", &c[i]);//输入一个有序数组
	}
	int a = 0;
	scanf("%d", &a);
	for (int i = b; i >=0; i--)//从最后一个开始比较
	{
		if (a>c[i-1])
		{
			c[i] = a;//如果大于最后一个数，直接赋值，程序循环结束，打印数组
			break;
		}
		else
		{//如果小，那就交换
			c[i] = c[i - 1];
			c[i - 1] = a;
		}
	}
	for (int i = 0; i < b + 1; i++)//打印最后的数组
	{
		printf("%d ", c[i]);
	}
	return 0;
}

发表于 2021-12-25 21:13:04 回复(0)

鲸鱼lord

#include <stdio.h>
//方法一：二分查找+静态数组（适用于数据量很大的情况）
int main() {
    int n;
    // 读取序列长度，题目限制 n 最大为 50，数组开 51 是为插入元素留空间
    scanf("%d", &n);
    int arr[51];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int num;
    scanf("%d", &num);

    // 二分查找确定插入位置
    int left = 0, right = n;
    int pos = n; // 初始设为数组末尾，若 num 比所有元素大，就插在最后
    while (left < right) {
        int mid = left + (right - left) / 2;//防止溢出
        if (arr[mid] >= num) {
            pos = mid;
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    // 元素后移：从数组末尾开始，把插入位置及之后元素依次后移
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }
    // 插入新元素到 pos 位置
    arr[pos] = num;

    // 输出结果：按顺序打印 N + 1 个有序整数
    for (int i = 0; i <= n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}


//方法2：动态内存+直接遍历（适用于此题，数据量小）

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n;
    scanf("%d", &n);

    // 动态分配初始数组内存
    int* arr = (int*)malloc(n * sizeof(int));
    if (arr == NULL) {
        printf("内存分配失败\n");
        return 1;
    }

    // 读取原始有序序列
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int num;
    scanf("%d", &num);

    // 动态扩容数组（增加1个元素的空间）
    int* new_arr = (int*)realloc(arr, (n + 1) * sizeof(int));
    if (new_arr == NULL) {
        printf("内存扩容失败\n");
        free(arr); // 释放原始内存，避免泄漏
        return 1;
    }
    arr = new_arr; // 指向扩容后的内存

    // 直接遍历找到插入位置（简单直观，适合数据量不大的场景）
    int pos = n; // 默认插在末尾
    for (int i = 0; i < n; i++) {
        if (arr[i] >= num) {
            pos = i;
            break;
        }
    }

    // 元素后移
    for (int i = n; i > pos; i--) {
        arr[i] = arr[i - 1];
    }

    // 插入元素
    arr[pos] = num;

    // 输出结果
    for (int i = 0; i < n + 1; i++) {
        printf("%d ", arr[i]);
    }

    // 释放动态分配的内存
    free(arr);
    return 0;
}

发表于 2025-08-23 22:38:21 回复(0)

StellarVibes

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    int n = 0;
    scanf("%d", &n);
    int arr[100] = { 0 };
    int b = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);

    }
    scanf("%d", &b);
    for (int i = 0; i < n;i++)
    {
        int j = 0;
        for (j = 0; j < n - i-1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
    if (n == 1)
    {
        if (b > arr[0])
        {
            printf("%d %d", arr[0], b);
        }
        else
        {
            printf("%d %d", b, arr[0]);
        }
    }
    else
    {
        if (b < arr[0])
        {
            printf("%d ", b);
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d ", arr[i]);
            if (b > arr[i] && b < arr[i + 1])
            {
                printf("%d ", b);
            }
        }
        if (b > arr[n - 1])
            {
                printf("%d ", b);
            }
    }
    return 0;
}

编辑于 2024-01-22 20:56:28 回复(1)

nvvn

int main() {
    int i = 0;
    int j = 0;
    int n = 0;
    int num = 0;
    int numplus = 0;
    int nums[50];
    int sums[51];
    scanf("%d", &num);
    for (i = 0; i < num; i++) {
        scanf("%d", &nums[i]);
    }
    scanf("%d", &numplus);
    sums[0] = numplus;
    for (i = 0; i < num ; i++) {
        sums[i + 1] = nums[i];
    }

    for (i = 0; i < num + 1; i++) {
        for (j = 0; j < num - i; j++) {
            if (sums[j] > sums[j + 1]) {
                n = sums[j + 1];
                sums[j + 1] = sums[j];
                sums[j] = n;
            }
        }
    }

    for (i = 0; i < num + 1; i++) {
        printf("%d ", sums[i]);
    }

    return 0;
}

讲输入的数组和输入的单个数字插入到新的数组再进行排序

发表于 2025-08-22 17:39:52 回复(0)

梦洋1

#include <stdio.h>

#include <stdlib.h>

int compact(const int *e1,const int *e2)

{

return *e1-*e2;

}

int main() {

int n;

scanf("%d",&n);

int arr[51];

for(int i=0;i<=n;i++)

{

scanf("%d",&arr[i]);

}

qsort(arr,n+1,sizeof(arr[0]),compact);

for(int i=0;i<=n;i++)

printf("%d ",arr[i]);

return 0;

}

发表于 2025-03-02 21:37:11 回复(0)

Anout

int main() {
    int n, m;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &m);

    int end = n;
    int i = 0, j = 0;
    for (i = 0; i < n; i++) {
        if (m >= arr[i] && m < arr[i + 1]) {
            for (j = end; j > i; j--) {
                arr[j + 1] = arr[j];
            }
            arr[i + 1] = m;
            break;
        } else if (m > arr[n - 1]) {
            arr[end] = m;
        } else if (m < arr[0]) {
            for (j = end; j >= 0; j--) {
                arr[j + 1] = arr[j];
            }
            arr[0] = m;
        }
    }

    for (int i = 0; i < n + 1; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

发表于 2024-08-08 10:58:52 回复(0)

清风xu来

#include <stdio.h>

int main() {

int n,i,j;

scanf("%d",&n);

int arr[n+1];

for(i=0;i<n;i++)

{

scanf("%d",&arr[i]);

}

int key;

scanf("%d",&key);

i=0;

while(arr[i]<key && i!=n)

{

i++;

}

j=n;

while(j>=i)

{

arr[j+1]=arr[j];

j--;

}

arr[i]=key;

for(i=0;i<n+1;i++)

{

printf("%d ",arr[i]);

}

return 0;

}

发表于 2024-05-17 01:26:52 回复(0)

提交观点

问题信息

上传者：牛客309119号

难度：

101条回答 190收藏 4358浏览

通过挑战的用户

查看代码

牛客82216...

2023-03-11 17:21:12
lengthing

2023-03-10 02:01:58
new-c-code

2023-03-08 17:33:30
幸运的可乐整顿职场

2023-02-18 18:28:59
Clown0040

2023-02-09 19:47:17

有序序列插入一个数

输入描述:

输出描述:

输入

输出

#include

问题信息

热门推荐

通过挑战的用户

相关试题