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

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

在数组中找数的问题

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

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

排序, PWs=0.Wj  
Idxmin=0,IdxMax=N JKs&!!  
again: >"+bL6#  
A[IdxMin]+A[IdxMax] X !l#1  
>a则IdxMax--; aD8r:S\  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- G G[$-  
<a则IdxMin++; )F4P-u  
D$y-Kh  
IdxMin<=IdxMax则结束 ?TVR{e:  
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) w5G34[v  
假设给定数S,排序后的数组为a,共n个元素 H ;}ue  
以a1-S/2为搜索区间, *m Tc4&*  
在此区间每个元素ai****如下操作 n6+M qN  
在区间[S/2,an]中用折半查找S - ai,如果找到aj,那么满足条件输出,继续 5N }|VGN  
因此时间复杂度依旧是O(nlogn) L.&Vi"M <@  
如此整个算法的时间复杂度还是O(nlogn)
级别: 终身会员

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

排序, \8Y62  
Idxmin=0,IdxMax=N v-(dh5e` H  
again: uidoz f2}  
A[IdxMin]+A[IdxMax] iewwL7  
>a则IdxMax--; }-/oL+j  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- OJ?U."Lxm$  
<a则IdxMin++; 4LXC;gZ  
<5O:jd  
IdxMin<=IdxMax则结束 ,Jrm85 oG  
goto again }y>/#]X  
5Sz&j  
对的
级别: 终身会员

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

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