作者dryman (dryman)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Mon May 10 08:25:59 2010
# form y hash of array
# key -> value of y array
# value -> array of y indexes which point to the associative value
$idx = 0;
for $item (@y) {
push @{ $y_hash_of_arr{$item} }, $idx++; # push $idx into
} # y_hash_of_arr
$idx = 0;
for $item (@x) {
push @{ $inter_of_x{$item} }, $idx if exists $y_hash_of_arr{$num-$item};
$idx++;
}
@i = values %inter_of_x;
for $item (keys %inter_of_x){
push @yvalues, $num-$item;
}
@j = @y_hash_of_arr{@yvalues};
# inter_of_x 是只找出 x array 中符合 $num-$item 的杂凑
# 其键为 $item （就是 x array 的 value）
# 其值为 array of idx ，使用阵列是因为可能有多个idx含有同个值
#
# 根据inter_of_x可得到符合要求的yvalue
# 再由yvalue找到arr of idx of y
===============================
原始题目只要exists就好
@Hoy(@y)=(); # 只要键不用值
for (@x) { print "exists" and last if exists $Hoy{$num-$_}; }
这样的话只会印出 "exists" 一次就会跳出回圈了XD
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.136.177.207
1F：→ dryman:BTW hash值重复时，旧的值会被覆盖掉，但若是单纯判断有无 05/10 08:27
2F：→ dryman:就没关系 05/10 08:27
3F：→ dryman: 05/10 11:50
4F：→ dryman:抓出多个idx的版本很丑..不知道Perl有没有比较好的idx func 05/10 11:51
5F：→ yauhh:你这样题意也改掉了,输入资料的内容也改掉了,谈Big-O没意义 05/10 12:10
6F：→ yauhh:你知道什麽是Big-O吗? Big-O是指普遍的情况下,你的程式需要 05/10 12:10
7F：→ yauhh:执行的步骤数目与输入的资料量有什麽关连. 05/10 12:11
8F：→ yauhh:如果要先假设输入是什麽,那我也可以假设X,Y阵列全都是1, 05/10 12:11
9F：→ yauhh:这样演算法多简单啊,还全都O(1)呢! 05/10 12:12
10F：→ yauhh:可是这样玩没有意义. 05/10 12:12
11F：→ yauhh:而你抓着perl语法自high,在演算法方面有什麽意义? 05/10 12:14
12F：→ dryman:哪里要假设输入资料是什麽请你说清楚 05/10 13:06
※ 编辑: dryman 来自: 140.112.46.31 (05/10 13:28)
13F：→ dryman:演算法之前有推过，这里再提一次：由yhash找出Y当中符合 05/10 13:28
14F：→ dryman:资格的值，制作yhash及跑过整个x的big-O个别为O(m),O(n) 05/10 13:29
15F：→ dryman:hash的key是arr val, 值的话在本篇是多个idx的集合 05/10 13:30
16F：→ dryman:但存取值因为是O(1)，判断key是否存在也是O(1) 05/10 13:31
17F：→ dryman:故整体的big-O只有O(m)+O(n) 05/10 13:32
18F：→ dryman: 05/10 13:32
19F：→ dryman:之前写的演算法无法输出重复的idx，但这不是题目要求的 05/10 13:33
20F：→ dryman:因为题目只有说要找是否存在ij 05/10 13:36
21F：推 ledia:yauhh 每次都搞不清楚状况... 不意外, 你的做法很好了 05/17 11:26
22F：→ ledia:拿空间换时间, 算是一种很有效加速 05/17 11:26
23F：→ ledia:不过有的 hash 的 implementation 不见得是 O(1) 05/17 11:26
24F：→ ledia:不过概念到就是了 05/17 11:27
25F：→ dryman:是没错啦XD 制作时和存取都不一定是O(1) 05/17 17:35
26F：→ yauhh:没有搞不清楚喔.而是旁观者ledia你没看清楚我在问什麽. 05/18 08:07
27F：→ yauhh:dryman你说,喔,如果阵列每个值都unique就ok,全都是O(n)搞定 05/18 08:08
28F：→ yauhh:但是资料怎麽会乖乖去unique给你容易O(n)? 相对的,谈演算法 05/18 08:08
29F：→ yauhh:的人所遵守的游戏规则是,输入是什麽,要原封不动. 题目说 05/18 08:09
30F：→ yauhh:unsorted list,不知道有没有排序,那你给他定一个值unique有 05/18 08:10
31F：→ yauhh:何意义? 05/18 08:10
32F：→ yauhh:所以我说,喔,你要把值自己取unique一段说演算法会变成O(n), 05/18 08:11
33F：→ yauhh:那我也可以取两阵列值只存在一种值对应另一种值的情况,然後 05/18 08:11
34F：→ yauhh:说演算法可以O(1). 这两种都是没有意义,但是可以帮助自己 05/18 08:12
35F：→ yauhh:自high的. 05/18 08:12
36F：→ yauhh:你说的都有道理,但只是在特定情况之下有道理而已. 05/18 08:13
37F：→ yauhh:如果要谈值有重覆的,你敢不敢说你的办法仍保持在O(n)? 05/18 08:14
38F：→ yauhh:当题目说出(i,j)的字眼时,你觉得你回答一个"yes"或"no"会 05/18 08:16
39F：→ yauhh:得几分? 05/18 08:16
40F：→ yauhh:你只限定自己演算法找到就回答"yes",可是别人在找演算法来用 05/18 08:19
41F：→ yauhh:时,翻到你的演算法就会有个感觉:效果是不错,但是答非所问, 05/18 08:19
42F：→ yauhh:实际用途不会这样做. 05/18 08:19
43F：→ yauhh:怎麽样,半路杀出来呛声的ledia,你说说看我到底哪里没搞清楚? 05/18 10:09
44F：→ yauhh:还有,你一跳出来就只会说,因为是*我*搞不清楚,所以没错... 05/18 10:09
45F：→ yauhh:这不就叫做人身攻击吗? 长久以来你并没有进步呢. 05/18 10:10
46F：推 Huangs:我不懂强者 yauhh 在质疑什麽 dryman的方法 05/18 14:39
47F：→ Huangs:无论输入是否unique都可以运作啊 哪里答非所问了？ 05/18 14:40
※ 编辑: dryman 来自: 140.112.46.31 (05/18 22:10)