算法题:怎么区分互不相同的<a, b>数对,hash还是?

问题:有N个数对,其中a的范围是[0,100],b的范围是[0,255],N<10000,如何区分这N对数对?
我的需求最好是利用a和b的值通过某种算法产生一个数,每个数对产生不一样的值,这样就能相互区分了。
比如有下列这些数对:
<1,2>
<2,3>
<2,1>
<7,76>
<4,2>
<45,123>
...
等等,怎么设计一个利用a和b设计一个算法,来区分这些数对,比如a+b,当然我只是举个例子,简单的加减乘除都不行,因为有些数对比如<2,1>与<1,2>就不能区分了。
如果区分不了,那么能不能设计一个hash算法,使得这些数对全部映射到[0,M]之间,M最好<5000,这样就可能有不能区分的了,没关系,只要使得冲突最小也行。
重点:这样的需求不好解决问题,因为是随机的,没什么分布规律。但有一些分布特点:如果同一个a,b非常有可能是分段连续的,比如像下面这样:
<2,1>
<2,2>
<2,3>
<2,4>
<2,5>
<2,124>
<2,125>
<2,126>
<2,127>
<2,128>
<2,129>
<2,130>
...
我的要求:尽可能时间高效,比如用hash,一下就能判断。
当然有人会想到用最简单的mapm,m的大小就是数对的个数,但显然这样的方向时空性能都不太高,而且没有利用a和b的某些规律。
请大家发挥自己的想象力吧~~~
holdtom
浏览 525回答 2
2回答

紫衣仙女

算法:两步hash,你的数是很规范的,a和b的范围都是给定的。算全域hash,a也只有100个hash值,b有250个,所以总共只有100×250=25000个hash值,超过你的
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

JavaScript