1146: 零起点学算法53——数组中插入一个数

青旅半醒 2023-01-10 14:54 249阅读 0赞

## Description ##

给定有序数组（从小到大），再给你一个数，要求插入该数到数组中并保持顺序

## Input ##

多组测试，每组第一行输入一个整数n,然后是n个有序的整数  
第二行输入1个整数m和1个整数K

## Output ##

将整数m插入到原数组中保持顺序是升序，然后输出2行  
第一行是插入以后的数组  
第二行是插入以后的数组中下标值是K的数  
  
n m k不超过20

## Sample Input ![5f8f312f51791b8bb0ed0ae07c2ffa43.gif][] ##

3 1 2 5
    3 1

## Sample Output ##

1 2 3 5
    2

## Source ##

[零起点学算法][Link 1]

## Code ##

不知道为啥这个算不出正确结果

#include<iostream>
    #include<stdio.h>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[30];
            for(int i=0;i<n;i++)
                cin>>a[i];
            int m,K;
            int t=0;
            cin>>m>>K;
            for(int j=0;j<n;j++)
            {
                if(a[j]<=m&&a[j+1]>=m)
                {
                    for(int k=j+2;k<n+1;k++)
                        a[k]=a[k-1];
                    a[j+1]=m;
                    break;
                }
            }
            for(int i=0;i<n;i++)
                cout<<a[i]<<" ";
            cout<<a[n]<<endl;
            cout<<a[K]<<endl;
        }
    }

知道了，因为数组元素后移需要逆序遍历，但还是不对，因为没有考虑到最后一个元素也被比完了，剩下为空的情况，因此需要把数组初始化，比较的时候加入下一个元素为0的情况

AC代码

#include<iostream>
    #include<stdio.h>
    using namespace std;
    int main()
    {
        int n;
        while(~scanf("%d",&n))
        {
            int a[30]={0};
            for(int i=0;i<n;i++)
                cin>>a[i];
            int m,K;
            cin>>m>>K;
            ///考虑到j+1也要被限定，因此j<n-1)错了错了，这里想太多了
            for(int j=0;j<n;j++)
            {
                if(a[j]<=m&&a[j+1]>=m||a[j+1]==0)///插入到a[j]的后面
                {
                    for(int k=n;k>j+1;k--)
                        a[k]=a[k-1];
                    a[j+1]=m;
                    break;
                }
            }
            for(int i=0;i<n;i++)
                cout<<a[i]<<" ";
            cout<<a[n]<<endl;
            cout<<a[K]<<endl;
        }
    }

在网上找发现又是用两个数组做的，以m为隔断，前面存一次，后面存一次

#include<stdio.h>
    int main(){
        int n,a[50],b[50];
        while(scanf("%d",&n)!=EOF){
            for(int i=0;i<n;i++){
                scanf("%d",&a[i]);
            }
    
            int m,k,j=0;
            scanf("%d%d",&m,&k);
            for(int i=0;i<n;i++){
                if(a[i]<m){
                    b[j]=a[i];
                    j++;
                }
                else break;
            }
            b[j]=m;
            j++;
            for(int i=j-1;i<n;i++){
                b[j]=a[i];
                j++;
            }
    
            for(int i=0;i<j-1;i++){
                printf("%d ",b[i]);
            }
            printf("%d\n",b[j-1]);
            printf("%d\n",b[k]);
        }
        return 0;
    }

[5f8f312f51791b8bb0ed0ae07c2ffa43.gif]: /images/20221119/291904ebeac94525a32a34a85a17aea9.png
[Link 1]: https://oj.wustacm.top/problemset.php?search=%E9%9B%B6%E8%B5%B7%E7%82%B9%E5%AD%A6%E7%AE%97%E6%B3%95&searchmode=source&soj=0