上一主题下一主题
关键字
主题 : 在数组中找数的问题
级别: 北风技术菜鸟

UID: 470408
精华: 0
发帖: 277
威望: 1317 点
学点: 650 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2014-06-27
最后登录: 2015-04-07
楼主  发表于: 2015-03-23 12:55||

在数组中找数的问题

对一个整数数组,给定一个整数,在数组中找到两个数,这两个数之和等于所给定的这个整数,这样的数可能有多对,要求输出所有可能的组合。 H>?:U]  
要求考虑数组非常大,时间复杂度和空间复杂度;
此帖悬赏中(剩余时间:已结束)...
最佳答案: 2 学点
热心助人剩余点数: 1 学点
级别: 北风资深工程师

UID: 472685
精华: 0
发帖: 1930
威望: 1946 点
学点: 3280 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2014-07-10
最后登录: 2015-04-08
沙发(1楼)  发表于: 2015-03-23 12:55||

1. hash,然后线性搜索。 m< _S_c  
2. 排序,然后线性搜索。
级别: 北风资深工程师

UID: 472681
精华: 0
发帖: 1791
威望: 1815 点
学点: 2095 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2014-07-10
最后登录: 2015-04-07
板凳(2楼)  发表于: 2015-03-23 12:56||

排序, p'Y^ X  
Idxmin=0,IdxMax=N b!+hH Hv:  
again: =7?4eYHC  
A[IdxMin]+A[IdxMax] T 6'^EZZY  
>a则IdxMax--; :a!^   
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- P?%s #I:  
<a则IdxMin++; |44Ploz2b  
W<'m:dq  
IdxMin<=IdxMax则结束 [ |v][Hwv  
goto again
级别: 北风资深评论员


UID: 470398
精华: 0
发帖: 3024
威望: 3862 点
学点: 8642 点
贡献: 90 点
好评: 0 点
学币: 112 个
注册时间: 2014-06-27
最后登录: 2015-04-07
地板(3楼)  发表于: 2015-03-23 12:56||

用高效的算法排序,最快O(nlogn) J2d 3&6  
假设给定数S,排序后的数组为a,共n个元素 5}MjS$2og  
以a1-S/2为搜索区间, 7r,h[9~e  
在此区间每个元素ai****如下操作 X[r\ Qa  
在区间[S/2,an]中用折半查找S - ai,如果找到aj,那么满足条件输出,继续 ?KMGk]_<  
因此时间复杂度依旧是O(nlogn) k;c>=B)e  
如此整个算法的时间复杂度还是O(nlogn)
级别: 终身会员

UID: 241899
精华: 0
发帖: 80
威望: 795 点
学点: 0 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2010-06-10
最后登录: 2015-12-21
地下室(4楼)  发表于: 2015-03-31 15:55||

排序, q>wO=qWx  
Idxmin=0,IdxMax=N <[w5M?n8  
again: /%gMzF  
A[IdxMin]+A[IdxMax] )2#q i/  
>a则IdxMax--; ` TH\0/eE  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- Ikw.L  
<a则IdxMin++; ";7/8(LBZ  
|'I>Ojm  
IdxMin<=IdxMax则结束 j"fx|6l)  
goto again i`W~-J  
Y[_|sIy*  
对的
级别: 终身会员

UID: 241899
精华: 0
发帖: 80
威望: 795 点
学点: 0 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2010-06-10
最后登录: 2015-12-21
下水道(5楼)  发表于: 2015-03-31 15:56||

  希望对你有用
级别: 北风助理工程师

UID: 617007
精华: 0
发帖: 185
威望: 1202 点
学点: 1193 点
贡献: 0 点
好评: 0 点
学币: 0 个
注册时间: 2015-12-19
最后登录: 2017-05-02
6楼  发表于: 2016-05-20 14:27||

nike air force 1 mid dam

本部分内容设定了隐藏,需要回复后才能看到