号码算法 关于快速查找与匹配(3)

不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据号码快速查询会员里程积分的功能。

输入格式:

输入首先给出两个正整数N（≤10

??5

???? ）和K（≤500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：18位号码（空格）飞行里程。其中号码由17位数字加最后一位校验码组成，校验码的取值范围为0~9和x共11个符号；飞行里程单位为公里，是(0, 15 000]区间内的整数。然后给出一个正整数M（≤10

??5

???? ），随后给出M行查询人的号码。

输出格式:

对每个查询人，给出其当前的里程累积值。如果该人不是会员，则输出No Info。每个查询结果占一行。

输入样例:

4 500
330106199010080419 499
110108198403100012 15000
120104195510156021 800
330106199010080419 1
4
120104195510156021
110108198403100012
330106199010080419
33010619901008041x
输出样例:

800
15000
1000
No Info

原题链接： https://pintia.cn/problem-sets/959995131537092608/problems/959995183282221063

同样是一道考察快速查找匹配的题目，笔者开始仍然是使用哈希表的方法做，单较为繁琐，后来改为利用Set容器，但有一些小问题，之后再讨论，至于使用哈希表的做法，参照上题，稍作修改以及对散列函数重新分析，可以得到相同的效果，有兴趣可以自行尝试。号码算法

我们以7-16为例，可以稍微进行一些散列表的分析，对于查找与匹配等问题，我们需要保证两点，其一是其高效性，其二是其准确性，对于一般的问题，我们往往会采取开数组的方法来处理，而我们又知道，最快捷的访问方法是利用数组的随机访问方式，但可惜的是，我们对于绝大多数数据，无法使其得到单一的与数组下标对应的值，例如7-16，号为18位，若其为纯数字的话，或许有些高级语言原生支持大数存储，那么数组呢，开10^18次方的吗，显然不现实，何况校验码还为字母，这时我们就想在保证其准确性与效率的前提下，使其得到近似于随机访问的O(1)的效率，这时我们就需要使用哈希算法，将其关键字进行离散化，得到固定长度的函数值，并映射到对应的位置上，从而得到较高的效率。举个简单的例子，假设我们要在全校范围内寻找到高为一米八的人，我们可以采取如下方式，带着全校的人名单，一一查找（顺序查找）；第二，使全校同学按身高排好队（队头最高），并从队伍中间开始查找，若该同学高于一米八，则向队伍后面查找，若低于一米八，则向 队伍前面查找（二分查找），三，我们预先知道了一米八以上的人占全校人数的三分之一，那么我们直接走向队伍距离队首三分之一处，开始查找（插值搜索），或许这次我找到了一米八的人，但是下次我要找一米六的人呢，再重新排好队（排序），再进行查找吗，显然太费时间了，（何况你的学生们还会有意见），这时我们不妨再开学时来一次统计，例如，一米八到两米的同学的名字放在一张单子上，一米六到一米八的同学的名字放在一个单子上，以此类推，那么下次查找时，我直接拿来对应身高的单子，去查找即可，大大节约了时间。（例子不太恰当，实际上入学体检时已经记录好了，何况学生是会说话的），那么我们将数据进行散列处理的目的就在此，将一系列数据按照预先设定好的函数进行处理，得到固定长度的函数值，（按身高区间放入名单），那么我下次进行查找时，直接将关键字的值放入散列函数处理得到对应的值，并在该区间内查找（在名单内查找），这样可以将搜索范围大大缩小。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-86698-3.html