我要招人

去企业版

首页 > 试题广场 >

数组A由1000W个随机正整数(int)组成，设计算法，给定

[问答题]

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

周星星_

方法一、数组排序，二分

1000w数字存到数组中，需要的地址空间为1000w*4byte=4w kb =40 Mb。这个容量是可以接受的。

将数组快速排序，平均时间复杂度O(n*logn)

对任给的n，找n=a+b

假设v是排序后的数组，a,b组合无非是

v[0], n-v[0]

v[1], n-v[1]

...

v[i]>=n

通过二分查找来确定是否存在这一组a，b就是确定n-v[i]是否存在。最坏需要i*logn次。

所以总时间复杂度为O(nlog(n)*log(n)) //不严格

方法二、hash_map

原数组为a，如果a[i]<n，就把(a[i],0)键值对插入到哈希表h中，时间复杂度n

h的pair会按照key自动排序。我们主要是利用他查询复杂度O(1)的特点

确定每组a,b是否存在：

0,n

1,n-1

...

n/2-1,n/2+1

总时间复杂度为O(n)

方法三：

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

该方法不对，用数组下标标记元素i固然没错。但是问题在于整数n的上限可能很高，n=2^32时，申请一个大小为n的数组，需要的空间大小为2^32 * 4byte ≈ 4GB，太大了

ref：

http://group.jobbole.com/13848/

编辑于 2016-10-13 16:36:29 回复(5)

stupidjoey

用位图存1000W个正整数，O(n)

遍历位图，如果对应位为1，则标记为a，查找位图n-a的地方是否为1，位图遍历前一半即 n/2就可以了，O(n)

总体O(n)

编辑于 2015-10-21 15:52:47 回复(1)

SunburstRun

将数组排序，杂度n*logn在从头开始,假设第i个位置时arr[i],那就在 i到1000万之间找 n - arr[i] 二分查找的效率是logn,由于当arr[i] > n/2 时就不用找了,所以最终效率2*n*logn

发表于 2015-10-20 10:01:28 回复(0)

姚梦龙

//算法思路：考虑到数据量太大，辅助空间很容易不够。所以考虑只使用一个长为n的辅助数组temp来取巧。算法分为两步

//第一步，遍历A，每次将temp[ A[i] ]置为1，表示A[i] 出现了。

//第二步，遍历结束了此时。则遍历temp数组，遍历时每次都判断 temp[ i ] ]和 temp[ n- i ] ]是否都为1，若都为1则说明满足n=a+b的a和b都出现了，则输出。

时间复杂性：O(n)

发表于 2015-11-19 09:46:03 回复(5)

红豆20190807083095

int[]b=new int[n+1];
for(int i=0;i<A.length;i++){
    
    if(a[i]<=n){
        int c=a[i];
        b{c}=1;
        
    } 
}

for(int i=0:i<=n;i++){
    if(b{i}==1&&b[n-i]==0){
        sys.out.prirnt(""+i+(n-i));
    }
}

发表于 2019-08-24 10:43:21 回复(0)

windxd

 #include <iostream> 

using namesapce std;

int main()
{
    int n;
    vector<int> vec;
    sort(vec.begin(),vec.end());
    int i = 0,j = vec.size()-1;
    while(i<j)
{
    if(vec[i]+vec[j]<n)
         i++;
   else if(vec[i]+vec[j]>n)
         j--;
    else
        {
            cout<<vec[i]<<ends<<vec[j];
            i--;j--;
        }
}

return 0;
}

先对数组排序，然后设置两个游标分别从小端和大端开始向中间遍历，但对游标和小于n则小端游标++,大于你则大端--

时间复杂度为O(n)

发表于 2017-08-21 21:56:47 回复(0)

牛客707793号

可以将数组先进行从大到小排序，时间复杂度为O（lgn）

然后再定义两个指针P1，P2分别指向数组的第一个和最后一个，也就是最小值和最大值计算它俩之和如果结果大于n，则向前p2,如果他俩得的和小于n，则向后移动P1，直到p1>p2完成，找到其中符合条件的结果打印出来

发表于 2016-09-02 15:17:14 回复(0)

Echo001

1.将数组A中的数据，存入Hash表；
2.遍历A数组，假设当前取到的值为a =  A[i],则b = x-A[i]；
3.在Hash表中查找b，如果存在则返回，否则继续2-3，直至找到符合要求的解。
 
时间复杂度O(n)。

发表于 2016-09-01 17:38:22 回复(0)

沐浴星光的潇洒少年

首先，分析数组中是随机数，所以a,b有可能在数组中重复出现，所以需要定义两个数组A,B来存放查找到a和b时的数组下标，

接下来就是遍历整个数组，外层和内层循环遍历，如果循环中满足n=a+b,则记录a和b的下标分别放到A,B数组中，此时内层的循环还不能断，因为数组中可能有多个b值，继续遍历内层循环，找到循环中满足n=a+b的值，此时a的下标没变，b的下标已变，将a，b的下标分别放到A,B数组中去。

内层循环完毕之后，外层继续循环，如此就可以得到所有满足n=a+b的值。

数组A,B中记录的就是所有满足等式n=a+b的值的下标（一一对应）

时间复杂度是O(9999999*9999999),因为外层循环要从0走到9999999，里层循环也要从0走到9999999

发表于 2015-10-21 19:07:00 回复(1)

提交观点

问题信息

C++工程师数组 2016 Java工程师 58集团

来自：58同城2016研发工...

上传者：小小

难度：

9条回答 55收藏 13583浏览

数组A由1000W个随机正整数(int)组成，设计算法，给定

问题信息

热门推荐

相关试题