作者dryman (dryman)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Mon May 10 00:43:08 2010
※ 引述《yauhh (哟)》之铭言：
: ※ 引述《dryman (dryman)》之铭言：
: : 用Perl随便兜一个
: : 虽然这不能当演算法的解答啦
: : 不过就应用上还蛮不错的XD
: : @x = 1..60;
: : @y = 30..100;
: : $num = 50;
: : @xhash{@x}=0..$#x;
: : @yhash{@y}=0..$#y;
: : foreach $item (@x) {
: : push @pair,[$xhash{$item},$yhash{$num-$item}] if exists $yhash{$num-$item};
: : }
: 看你这一段程式有些小小疑惑,就当做hash真强到找什麽都O(1)好了,
: 先考虑一种情况:
: 首先把X,Y阵列的值都丢到xhash和yhash,
: 你找到一个$xhash{$item},$item表示X阵列的一格值,所以用$num-$item找yhash,
这行看不懂
我是对@x做回圈
foreach $item (@x)
可读作 for each $item in @x array
: 找到Y阵列中的另一格值$yhash{$num-$item}.
: 接下来有个问题是:$yhash{$num-$item}是Y的第几格?
hash 中没有格不格的问题啊@ @
$yhash{$num-$item}
是把$num-$item的值
丢进" if exists $yhash " 中
（这句不适合拆开来读，因为$yhash在前面有exists时是回传布林值
没有exists 时则是回传此键对应的值）
这一步的动作为O(1)
: 在这个情况中,看起来没有处理这个... 而是否没处理这个让你得到O(n)的印象?
: 考虑另一种情况:
: 也许我不懂perl,把它看错了,其实是把X,Y阵列的每一格,包含{index,value}都丢进
: hash. 所以$xhash{$item}是{i,v}这样的内容,把它拿去yhash找的时候,
: 一定要做两个动作:
: 1. 把v取出找$num-v
: 2. 在yhash找到合适的{j,$num-v}.
: 然後你才可以找到一对(i,j),其X[i]与Y[j]总和为$num.
: 在这种情况中,找到对应的{j,$num-v}显然不会是O(1)的,假设有k个这种j,
: 就要找j次. 这样算总数起码也是个O(m*k),m是X长度,k可视同为Y长度.
: 是哪种情况呢?
我想您可能是看错foreach $item (@x) 这一行吧XD
後面这里的解释我都看不太懂:P
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.136.185.230
1F：→ dryman:突然发现原始题目是exist i,j 而不是找全部的解... 05/10 00:47
@yhash{@y} = 0..$#y;
for $item (@x){
print "exist\n" if exists $yhash{$num-$item};
}
XDDDDD
超级有"语感"的!!
Perl是语言学家开发出来的程式语言用起来真的抄酷！
※ 编辑: dryman 来自: 220.136.185.230 (05/10 00:49)
2F：→ yauhh:可是你找答案是要告知是在Y的第几格. 05/10 00:52
3F：→ yauhh:你用yhash随便存一个值能有什麽用呢? 05/10 00:52
4F：→ yauhh:总之,我认为你没有找到少於O(m*n)的演算法,你只是把程式写出 05/10 00:55
5F：→ yauhh:来而已. 05/10 00:55
6F：→ yauhh:你想想看,我在演算法观点上写第二段,你随便说看不懂,那麽, 05/10 00:56
7F：→ yauhh:你随便丢出一段perl码,谁有必要看得懂? 05/10 00:57
8F：→ yauhh:我也可以说我把X包装成new some(X),然後它找任何值以及由值 05/10 01:01
9F：→ yauhh:找任何index全是O(1)...但那没意义,这是在谈演算法,不是程式 05/10 01:02
10F：→ dryman:你真的懂hash是什麽吗？... = = 05/10 01:02
11F：→ yauhh:我懂啊,但你知不知道我没在跟你谈hash 05/10 01:03
12F：→ dryman:经由hash function来确认是否有值本来就是O(1) 05/10 01:03
13F：→ yauhh:我在跟你讲的是,虽然你找得到值,但没找到对应於值的index.. 05/10 01:04
14F：→ dryman:我的key->arr val, value-> arr idx 05/10 01:04
15F：→ yauhh:可是这问题没有解决啊,又不是你hash弄完就把答案弄出来了 05/10 01:04
16F：→ dryman:这样就可以找到idx了啊 05/10 01:04
17F：→ dryman:push @pair, [$xhash{$item},$yhash{$num-$hash}] 05/10 01:05
18F：→ yauhh:对啊,问的就是这个啊 05/10 01:06
19F：→ dryman:这不就是用$item及$num-$item当hash key来找arr idx 05/10 01:06
20F：→ dryman:我最後面补充的，是因为原始题目是问i,j是否exists 05/10 01:07
21F：→ dryman:所以可以写得非常短...印出exist就好 05/10 01:07
22F：→ yauhh:ok,下一个问题是,如果一个value对应到好几个index,取这一堆 05/10 01:09
23F：→ yauhh:也是O(1)? 05/10 01:09
24F：→ dryman:噢，我的解法是假设X,Y的值都是unique 05/10 01:11
25F：→ dryman:在个别阵列中不会有重复的值，这我的确没考虑到 05/10 01:11
26F：→ yauhh:那你不可以假设,题目并没有假设这件事情. 05/10 01:12
27F：→ dryman:不过用hash还是可以解：利用hash做出值不重复的阵列 05/10 01:13
28F：→ dryman:同时记录每个value的index（用hash of array） 05/10 01:13
29F：→ dryman:做出不重复的阵列後再用本解法得出arr val，用hash of arr 05/10 01:14
30F：→ dryman:反推idx 05/10 01:14
31F：→ dryman:这样的话就是some small value * O(n) 05/10 01:15
32F：→ dryman:明早还有课，先不战了XD 05/10 01:16
33F：→ dryman:明天再来PO改版的城市 05/10 01:16