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

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

在数组中找数的问题

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

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

排序, 3@s|tm1  
Idxmin=0,IdxMax=N O^4:4tRpt  
again: 4 K{4=uU  
A[IdxMin]+A[IdxMax] `gD'q5.z;3  
>a则IdxMax--; LYkW2h`JQ  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- &D>e>]E|P  
<a则IdxMin++; E,u@,= j  
lySeq^y?Q  
IdxMin<=IdxMax则结束 r^VH [c@c  
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) |1$X`|S  
假设给定数S,排序后的数组为a,共n个元素 R2gax;  
以a1-S/2为搜索区间, oWT0WS  
在此区间每个元素ai****如下操作 `8*$$JC  
在区间[S/2,an]中用折半查找S - ai,如果找到aj,那么满足条件输出,继续 e;v 2`2z2  
因此时间复杂度依旧是O(nlogn) "^7Uk#! 7  
如此整个算法的时间复杂度还是O(nlogn)
级别: 终身会员

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

排序, q/qJkr^2  
Idxmin=0,IdxMax=N 6Z ,GD  
again: P80mK-Iyv_  
A[IdxMin]+A[IdxMax] 2,T^L (]  
>a则IdxMax--; "fH"U1Bw  
==a,(IdxMin,IdxMax)为符合数序号,IdxMin++,IdxMax-- K."%PdC  
<a则IdxMin++; ^ s.necg0  
DWXxB  
IdxMin<=IdxMax则结束 t?l0L1;  
goto again P[L] S7FTr  
)\3 RR.p  
对的
级别: 终身会员

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

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