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

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

在数组中找数的问题

对一个整数数组,给定一个整数,在数组中找到两个数,这两个数之和等于所给定的这个整数,这样的数可能有多对,要求输出所有可能的组合。 $JFjR@j  
要求考虑数组非常大,时间复杂度和空间复杂度;
此帖悬赏中(剩余时间:已结束)...
最佳答案: 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,然后线性搜索。 osdl dS  
2. 排序,然后线性搜索。
级别: 北风资深工程师

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

排序, @Uqcym.  
Idxmin=0,IdxMax=N 9,$ n 6t;  
again: KP CZiu7  
A[IdxMin]+A[IdxMax] /U= ?D(>x  
>a则IdxMax--; &G_XgQsg{  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- /\m>PcPa  
<a则IdxMin++; 41c4Xj?'  
p5#UH  
IdxMin<=IdxMax则结束 ?-=<7 ~$  
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) &uI`Xq.  
假设给定数S,排序后的数组为a,共n个元素 |Tuk9d4]  
以a1-S/2为搜索区间, Fr?o 4E6h  
在此区间每个元素ai****如下操作 (?Fz{  
在区间[S/2,an]中用折半查找S - ai,如果找到aj,那么满足条件输出,继续 23 BzD^2a  
因此时间复杂度依旧是O(nlogn) wy eiz7  
如此整个算法的时间复杂度还是O(nlogn)
级别: 终身会员

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

排序, > [|SF%  
Idxmin=0,IdxMax=N `%M} :T  
again: qnZ`]?  
A[IdxMin]+A[IdxMax] 8Bnw//_pT  
>a则IdxMax--; ;ckv$S[p  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- /@bLc 1"  
<a则IdxMin++; {@u}-6:wAT  
jdYv*/^  
IdxMin<=IdxMax则结束 \'L6m1UZ%  
goto again r}~l(  
6]}Xi:I  
对的
级别: 终身会员

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

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