我爱OJ 2023-03-11 19:23 采纳率: 78.8%
浏览 66
已结题

关于#Input#的问题,如何解决?

Description

给定两个整数可重复集合,求两个集合的交集。
Input

输入有两组数据,第一组的第一行为一正整数n,一下n个正整数ai(0 < i <= n)。

第二组的第一行为正整数m,以下m个正整数bi(0 < i <= m)。

其中 1 < n, m <= 32767 0 < ai, bi <= 32767
Output

输出一行,k个正整数,为两组数据构成集合{ai}和{bi}的交集。

输出按第二组数据出现的顺序输出,两数之间使用空格间隔,最后一个数无空格,重复数据只输出一次。

若交集为空,只输出一个0
Sample Input
10
1 2 3 4 5 6 7 8 9 10
10
9 10 11 12 13 14 15 16 17 1
Sample Output
9 10 1

时间超限,时间复杂度为o(n),该怎么改呢

#include <iostream>
using namespace std;
int main()
{
        int a[32768], b[32768], A[32768]={0}, c,d, e = 0;
    cin >> c;
    for (int i = 0; i < c; i++)
    {
        cin >> a[i];
        A[a[i]] = 1;
    }
    cin >> d;
    for (int i = 0; i < d; i++)
    {
        cin >> b[i];
    }
    for (int i = 0; i < d; i++)
    {
        if (A[b[i]] == 1)
        {
            if (e != 0)
            {
                cout << " ";
            }
            e++;
            cout<< b[i];
        }
    }
    if (e == 0)
    {
        cout << e;
    }
 
    return 0;
}
 

  • 写回答

3条回答 默认 最新

  • 社区专家-Monster-XH 2023-03-11 19:46
    关注
    
    #include <iostream>
    using namespace std;
    int main()
    {
        int a[32768], b[32768], A[32768] = {0}, c, d, e = 0;
        cin >> c;
        for (int i = 0; i < c; i++)
        {
            cin >> a[i];
            A[a[i]] = 1;
        }
        cin >> d;
        for (int i = 0; i < d; i++)
        {
            cin >> b[i];
        }
        for (int i = 0; i < d; i++)
        {
            if (A[b[i]] == 1)
            {
                if (e != 0)
                {
                    cout << " ";
                }
                e++;
                cout << b[i];
                A[b[i]] = 0; // 标记该数字已输出
            }
        }
        if (e == 0)
        {
            cout << "0";
        }
    
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

问题事件

  • 系统已结题 3月19日
  • 已采纳回答 3月11日
  • 赞助了问题酬金15元 3月11日
  • 创建了问题 3月11日

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名