- 论坛徽章:
- 0
|
原帖由 小丌 于 2007-1-22 14:46 发表
我有一个数组{4, 5, 10, 2 ... }，这些值事先知道，用什么方法映射到{0, 1, 2, 3 ... }这样子有规律的数组。
例如程序中变量 Val = 5； 我可不可以通过什么映射关系（不使用循环）得到对应的值1.
高人指教 ...
我不是高人，共同学习
第一种情况，映射可以用数学表达式描述（线性的）：
将数学表达式用程序实现，
第一种情况，映射不能用数学表达式描述：
比如第一个数组是A[10] = {4, 5, 10, 2, 53, 8, 9, 3, 18, 14}, 要映射到的数组是B {0, 1, 2, 7}
映射关系（记为f）:
A 4 5 10 2 53 8 9 3 18 14
B 7 2 1 0 2 7 1 2 0 7
即, 4 映射到7, 5映射到2, 10映射到1, ...
这个映射关系很简单,并且数组元素较少(最重要的一点 )
可以一个二维数组将以设关系放进去,做成一个表
如，int c[10][2];
c[0][0] = 4, c[1][0] = 7;
c[0][1] = 5, c[1][1] = 2;
...
用的时候直接查表。
如，查5的对应值：
for (int index = 0; index < 10; i++ ){
if (c[0][index] == 5){
return c[1][index]; //ans: 2 
}
}
。
也可以用一维数组，int c2[10];
4对应7，4在A中的索引值为0, 则 c2[0] = 4;
5对应2，5在A中的索引值为1, 2在B中的索引值为2, 则 c2[1] = 2;
...
查5的对应值：
for (int index =0; index < 10; i++){
if (a[index] == 5){
return c2[index]; //ans: 2
}
}
。
速度快点的版本：（以空间换时间）
取数组A中的最大值53，建数组：
int c3[53+1];
4对应7，c3[4] = 7;
5对应2，c3[5] = 2;
10对应1，c3[10] = 1;
...
查5对应值：
return c3[5]; //快吧 
。
如果A中的最大值为2000，并且A中的元素很少，用楼上的哈希函数吧
(见笑了 )
==========================================
一个Hash函数链接： http://www.ccw.com.cn/htm/app/aprog/01_8_22_3.asp
[ 本帖最后由 libin1983 于 2007-1-22 22:47 编辑 ] |
|
免费注册
发表于 2007-01-22 14:46
