有A、B两个文件,文件格式相同,均为每行一个十进制整型数字,两个文件的行数不一定相等,但均在一千万行左右。A文件中的数字两两不等,B文件中的数字两两不等, 请用一个算法找出A和B两文件中所有相同的数,并且从小到大有序输出。

请考虑统计程序如何实现,给出设计思路和关键算法(可使用伪代码),并估计程序核心代码的时间复杂度和空间复杂度。

2 12 收藏


直接登录
最新评论
  • 中华年末   2015/12/14

    一种暴力迭代,时间复杂度为O(n^2);
    一种空间换时间,时间复杂度O(n),空间复杂度O(n)。

  • 7CodeFish   2015/12/15

    1.放入1万,2万等以万结尾的数进文件。
    2.排序,每次AB取出以万为区间的数(无论多少,有没有)
    3.分别填充进100*100的矩阵中,矩阵中的元素存在用1表示 0表示不存在,
    4.怎么比较这两矩阵中同样的元素呢???
    5.个人推想……卡在最后一步数学上了。

    • ShadowLin   2015/12/16

      如果用二维数组效率肯定是最低的,如果会hadoop的话这个题目很容易,不会hadoop就考虑hash表或者map的数据结构

  • 冬日里的蓝色牧场 程序员 2015/12/15

    给我的第一印象是可以用哈希

  • BlackJoker   2015/12/15

    假设所有整数的范围是-2^31到2^31-1,可以创建两个长度为2^31的BitSet,一个存储负数,一个存储正数,消耗内存是512M。
    然后开始遍历文件A,然后这是两个BitSet,使用流式文件API,消耗内存是O(1)。

    之后遍历文件B,用B中的数字去上面两个BitSet中检查,如果发现存在则记录下来。

    遍历完后,对记录下来的数字排序。

    时间复杂度O(n)+O(mlg m) :n是两个文件的行数,m是相同数字数目。
    消耗内存大概是:512M+O(m)

  •   2015/12/15

    把两个数列先排序,从a列开始在另外b列找相同的,找到n以后,从b列的n以后的数对a列做相同的操作,再反过来。。。这样会快一点吧 小菜鸟瞎说的

  • 王先生 学生 2015/12/16

    简单说一下自己的想法(欢迎吐槽)
    有一种叫做位图法的方法来解决这个问题,简单说一下伪代码
    //init
    for i=[1,maxInt]
    bit[i]=0
    do
    从A读出一个数n
    bit[n]=1
    loop until EOF (A)
    do
    从B读入一个数n
    bit[n]++
    loop until EOF(B)
    for i=[1,maxInt]
    if bit[i]==2
    then 输出i
    end
    时间和空间复杂度都是O(n)

  • 基数排序的话,就是O(n)
    桶排序的话,时间会快一些,空间如果不算指针域,就是O(n/10)

  • 是不是可以用图像识别的思路?

  • 卒~   2016/12/09

    1000万个整形数字,大概就38MB左右。用HASH,在排序,取决于排序算法。