1124: 两个有序数组合并

59 阅读 0 评论 39 点赞

我是靠谱客的博主谦让御姐，最近开发中收集的这篇文章主要介绍1124: 两个有序数组合并，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

已知数组a中有m个按升序排列的元素，数组b中有n个按降序排列的元素，编程将a与b中的所有元素按降序存入数组c中。

输入

输入有两行，第一行首先是一个正整数m，然后是m个整数；第二行首先是一个正整数n，然后是n个整数，m, n均小于等于1000000。

输出

输出合并后的m+n个整数，数据之间用空格隔开。输出占一行。

样例输入 Copy

4 1 3 5 7
3 6 4 2

样例输出 Copy

7 6 5 4 3 2 1

我是菜鸡，有很多说的可能不到位，希望大家能够指出来，我把我今天学到的东西列出来说一说，为什么单列了这道题呢，因为我发现了问题。

这道题当我把数组设为局部变量时，int[2000000]时，写完整个程序，在运行时会发现程序会超时，在oj上无法通过，但是当我把数组设为全局变量时，程序就可以运行了。具体我把我的代码放上

#include<stdio.h>
void sort(int a[],int n)
{
    int i,j,temp;
    for(i=0;i<n-1;i++)
        for(j=i;j<n;j++)
            if(a[i]<a[j])
            {
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
}
int a[2000000]; //这里注意把数组全局变量和局部变量不同 
int main()
{
    int m,i,n,j;
    scanf("%d",&m);
    for(i=0;i<m;i++)
        scanf("%d",&a[i]);
    scanf("%d",&n);
    for(i=m;i<m+n;i++)
        scanf("%d",&a[i]);
    sort(a,m+n);
    printf("%d",a[0]);
    for(j=1;j<m+n;j++)
        printf(" %d",a[j]);
    return 0;
}

之后我上网上查阅了资料，我发现对于全局变量和静态变量，两种变量的存储方式不同，对于全局变量，存储在内存中的静态区（static），而局部变量存储在栈区（stack）。

C语言程序占用内存分为几个部分：

堆区：由程序员分配和释放，比如malloc函数
栈区：由编译器自动分配和释放，一般用来存放局部变量，函数参数
静态区：用于存储全局变量和静态变量
代码区：用来存放函数体的二进制代码

在Windows系统下，经过测试，栈区的大小，经过测试，栈区的一般在2M内，也就是数组最大也不要超过int[200000].

而在静态区，可以开2^32字节大小的空间，我开了2000000的数组依然可以。

因此，当需要声明一个超过十万左右的数组时，尽量设置为全局变量。

最后放上本题的正确代码

#include<stdio.h>
int a[1000001], b[1000001];
int main()
{
    int n, m;
    int i, j;
    int k = 0;
 
    scanf("%d", &n);//升序数组逆序输出
    for ( i = n - 1; i >= 0; i--)
    {
        scanf("%d", &a[i]);
    }
 
    scanf("%d", &m);
    for ( j = 0; j < m; j++)
    {
        scanf("%d", &b[j]);
    }
 
    int c[n + m];
    int s = 0, t = 0;
    while (s < n && t < m)
    {
        if(a[s] >= b[t])
        {
            c[k++] = a[s++];
        }
        else
        {
            c[k++] = b[t++];
        }
    }
    while (s < n)
    {
        c[k++] = a[s++];
    }
    while (t < m)
    {
        c[k++] = b[t++];
    }
    for ( k = 0; k <= m + n - 1; k++)
    {
        printf("%d ", c[k]);
    }
 
    return 0;
}