首页 > 试题广场 >

有序序列插入一个数

[编程题]有序序列插入一个数
  • 热度指数：25504 时间限制：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头像 叶之秋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)
C
六子的猫猫会后空翻头像 六子的猫猫会后空翻
这道题理论上可以先定义一个 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)
C
xiaolock883头像 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)
C
在敲键盘的coder很幸运头像 在敲键盘的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头像 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头像 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)
C
宇南头像 宇南
为什么我这代码当输入数据
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)
C
喝醉了Ta的梦,晚安头像 喝醉了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)
C
阿金要努力头像 阿金要努力 
#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)
C
夜雨潇湘人断肠头像 夜雨潇湘人断肠
#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)
C
Anout头像 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来头像 清风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)
C
徐文达头像 徐文达 
#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <malloc.h>

int main()
{
    int n = 0;
    int same_n = 0;
    int* p = NULL;
    int tem = 0;
    int i = 0;

    scanf("%d", &n);

    //开辟空间，用来存放数组
    p = (int*)malloc(sizeof(int) * (n + 1));
    if (!p)
    {
        perror("malloc");
        return 1;
    }

    //录入有序数组
    for (i = 0; i < n; i++)
    {
        scanf("%d", p + i);
    }

    //录入待插入的整数
    scanf("%d", &tem);

    //寻找待插入的位置
    for (i = 0; i < n; i++)
    {
        if (tem < *(p + i))
        {
            //此时的i，就是tem应该在数组里的位置（下标）
            break;
        }
    }

    //进行插入操作
    same_n = n;
    while (same_n != i)
    {
        //数组从后往前拉
        *(p + same_n) = *(p + same_n - 1);
        same_n--;
    }
    *(p + i) = tem;

    //输出结果
    for (i = 0; i <= n; i++)
    {
        printf("%d ", *(p + i));
    }

    //释放空间
    free(p);
    p = NULL;
    
    return 0;
}

编辑于 2024-03-19 14:07:24 回复(0)
C
阿明a_6头像 阿明a_6 
#include <stdio.h>

int main() {
    int n = 0;
    int arr[60] = {0};
    while (~scanf("%d", &n))//输入有序数的个数
    {
        int i = 0;
        for (i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);//输入有序数
        }
        int x = 0;
        scanf("%d", &x);//要插入的数
        for (i = 0; i < n; i++) 
        {
            if (x < arr[0]) //当小于此组所有的有序数
            {
                for (i = 0; i < n; i++) 
                {
                    arr[n - i] = arr[n - 1 - i];
                }
                arr[0] = x;

            } 
            else if (x > arr[i] && x < arr[i + 1]) 
            {
                for (int j = n - 1; j > i; j--) 
                {
                    arr[j + 1] = arr[j];
                }
                arr[i + 1] = x;
            } 
            else if (x > arr[n - 1]) //当大于此组有序数的所有数
            {
                arr[n] = x;
            }
        }

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

发表于 2023-07-14 18:54:27 回复(0)
干饭的芭乐很细致头像 干饭的芭乐很细致
#include <stdio.h>

int main() {
    int a;
    int i =0;
    int arr[100] ={0};
    while (scanf("%d", &a) != EOF) {
        for(int i =0;i< a; i++)
        {
            scanf("%d",&arr[i]);
        }
        int m = 0;
        scanf("%d",&m);

        for( i =a-1; i>=0; i--)
        {
            if(arr[i] <m)
            {
                 arr[i+1] = m;
                 break;
            }  
            else
            {
                 arr[i+1] = arr[i];
            }
                 
        }
        if(i == -1)
            {
                arr[0]=m;
            }    
       

        for(int i=0; i<a+1; i++)
        {
            printf("%d ", arr[i]);
        }
       
    }
    return 0;
}
发表于 2023-05-31 10:12:06 回复(0)
提交观点

问题信息

上传者：牛客309119号
难度：
98条回答 3657浏览

热门推荐

通过挑战的用户

查看代码

相关试题

有序序列插入一个数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号