作者dryman (dryman)
看板CSSE
标题Re: [问题] 未排序的阵列，演算法相关问题
时间Sun May 9 23:31:35 2010
※ 引述《mqazz1 (无法显示)》之铭言：
: given two unsorted arrays X and Y,
: each contains m and n numbers, separately.
: design an algorithm so that,
: given a number d,
: it could determine if there exists two integers i and j,
: such that X[i] + Y[i] = d
: use less than O(m*n) running time
: 我想请问这题大致上从哪方面下手会比较简易
: 谢谢
用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};
}
语法解释如下：
# 假设x=1~60, y=30~100, d=50; 这部份可以随便改
# 要处理是否重复太麻烦了...
@x =
1..
60;
@y =
30..
100;
$num =
50;
# 杂凑键为阵列值，杂凑值为阵列索引
@xhash{
@x}=
0..
$#x;
@yhash{
@y}=
0..
$#y;
# 这三行其实就已经把问题解完了XDDD
foreach $item (
@x) {
push @pair,[
$xhash{
$item},
$yhash{
$num-
$item}]
if exists $yhash{
$num-
$item};
}
这边语法比较复杂
@pair是一个array of array
比较好懂的版本是写
if (exists $yhash{$num-$item}){
push @xidx, $xhash{$item};
push @yidx, $yhash{$item};
}
# 印出
foreach $item (
@pair) {
print
$item->[
0] .
" "
.
$x[
$item->[
0]].
" "
.
$item->[
1].
" "
.
$y[
$item->[
1]] .
"\n" };
使用arr of arr 似乎不会让印出工作变得比较简单 ~"~
唯一比较长比较丑的地方...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.46.31
※ 编辑: dryman 来自: 140.112.46.31 (05/09 23:34)
1F：→ dryman:如果是要写成演算法的话，也是hash key = arr val 05/09 23:41
2F：→ dryman:hash val = key 05/09 23:41
3F：→ dryman:说错hash val = arr idx 05/09 23:42
4F：→ dryman:制作hash O(n)+O(m), 由x来寻找的话O(n) 05/09 23:43
5F：→ dryman:数组不大的话hash几乎是O(1)真是太方便了（茶） 05/09 23:44