数组A由1000W个随机正整数(int)组成,设计算法,给定整数n,在A中找出符合如下等式:n=a+b的a和b,说明算法思路以及时间复杂度是多少?

3 收藏


直接登录
最新评论
  • sdkl   2016/03/01

    说下我的思路来抛砖引玉

    首先筛选掉比n大的数,然后把数据划分为5组
    a.比0.5n小的奇数
    b.比0.5n小的偶数
    c.比0.5n大的奇数
    d.比0.5n大的偶数
    e.等于0.5n的数

    e等于0.5n的就看个数就行了,主要处理其余4组。

    根据n的奇偶把abcd分成2组分别比较。例如n是奇数就比较ad,bc。

    ad的比较,把a排序一遍,然后根据d中的数据在a折半查找看有没有匹配项。
    得出结果后再比较另外一组。

    时间负责度我也不知道多少。。。

  • 我算了一下,10000000万个整数也就39MB不到,申请一个数组应该是可以的吧。
    那么用hash的方法(重复了没关系),排序后直接找n-a是否字数组中,不知道这样是否可以

    • 王先生 学生 2016/03/01

      应该是可以的 排序后用二分法来确定n-a是否在数组中额

    • WhuCS 孙雨佳 学生 2016/03/05

      你的思路大抵正确,用一个字典存储这些数字,时间复杂度是o(n),遍历这些数字,对于每一个数字a,判断n-a在不在字典里。判断字典里有木有关键字的时间复杂度o(1),所以总的时间复杂度是o(n),总结一下,只要是用到排序,时间复杂度都会较高。另外一千万个整数,即使每个数字占用四个字节,内存也需要400M啊。。。。。

      • 1000 00000个整数并不需要400M吧。。。40MB而就可以了

      • 搞笑了,排序干什么。直接申请一个大小为N的数组,只要40M空间,然后数组中每一个元素对N取余(当然如果比N还大就直接舍弃),取余的值就放在对于数组下标中。比方N为10,元素8,就放数组第8个元素中,然后看看数组第二个元素有没有值就好了。所以复杂度为o(n)

  • 王先生 学生 2016/03/01

    先对数组A中的1000W个正整数进行排序,时间复杂度为nlgn,然后从排序后的数组的开始进行查找,采用二分法,而且超过n/2的部分可以不用考虑,因此最终的复杂度不会超过2nlgn,个人看法,大家有什么好的办法可以提出来一起分享啊

    • 小二丬 2016/03/06

      先QuickSort或者TimSort,时间O(nlogn),空间O(logn)
      再用两个指针指向头和尾,向中间移动比较,得到所有pair(a, b),时间O(n),空间O(1)
      总时间O(nlogn)+O(n),总空间O(logn)+O(1)

  • 阿斌哥 硕士 2016/03/02

    如果能用8G左右的内存,利用桶排序的思想,时间复杂度应该可以控制在O(n)

    • 王先生 学生 2016/03/02

      题目的意思应该在内存一定的情况下来进行的,8G的内存个人认为在程序设计中不太实际

  • 其文   2016/03/02

    var A,n;
    A = [3,2,5,6,9,8,4,2,1,6,7,8,10,11];
    n = 8;
    var arr = [];
    var res = [];
    for(var i in A){
    arr[i] = i;
    }
    for(var j = 1; j < arr.length; j ++){
    if(j <= n/2){
    var t = n – j;
    if(arr[t]){
    res.push([j,t]);
    }
    }else{
    break;
    }
    }
    console.log(res);

    唯一的bug就是当n=8,但是只有一个4的时候也成立了,,,

    • 李俊   2016/03/04

      你把数组A里面的某一个数字去掉,比如:7,运行后你会发现奇迹般的冒出了个7,
      注意题目是随机数

  • wupengfei IT 2016/03/04

    多线程 分段并行处理~

  • 排序,然后两边夹逼,一前一后指针,小了前面的后移,大了后面的前移,复杂度O(nlogn)

  • 袁言 工程师 2016/03/05

    d = {}
    for item in A:
    if n – item in d:
    yield n – item, item
    else:
    d[item] = True

  • JY   2016/03/06

    boolean[] a = new boolean[Integer.MAX_VALUE];
    for (int i : A) a[i] = true;
    for (int i = 0; i < n / 2 + 1; i++) {
    if (a[i] && a[n – i])
    System.out.println("a=" + i + ", b=" + (n – i));
    }

  • 1.把数组A变成bitmap存储
    2.把大于n的数丢弃
    3.将bitmap分半
    4.将其中的一个反转
    5.在按位与

  • Alex   2016/03/27

    排序+二分;排序+尺取;排序然后数据离散化然后可以1kw的数组O (1)hash;
    不排序用个set

  • liucyu   2016/04/01

    1:排序
    2:保存由小于n的正整数组成的数组
    3:找到n/2位置的数字 由0开始遍历到此位置

  • 怎么去掉n后面在数组中的数