将一系列整数映射到单个整数

Question

我有一个函数，它接收一个整数作为输入，根据这个输入的范围来给它分配一个难度值。我知道可以用if else循环来实现这个功能。不过，我在想有没有更高效或者更简洁的方法来做到这一点。

我试着做了类似这样的事情

TIME_RATING_KEY ={
    range(0,46):1,
    range(46,91):2,
    range(91,136):3,
    range(136,201):4,
    range(201,10800):5,
}

但我发现我们可以把范围当作字典中的键（对吧？）。所以有没有更好的方法来实现这个呢？

Answer 1

你可以实现一个区间树。这种数据结构能够返回所有与给定输入点相交的区间。在你的情况下，区间之间没有重叠，所以它们总是会返回一个区间。

中心区间树的运行时间是O(log n + m)，其中m是返回的区间数量（在你的情况下是1）。所以这会把复杂度从O(n)降低到O(log n)。

区间树的基本思路如下：

• 首先考虑一个包含所有区间的整体区间
• 找到这个整体区间的中心点，然后把给定的区间分成三类：在中心点之前结束的、包含中心点的和在中心点之后开始的。
• 对在中心点之前结束的区间和在中心点之后开始的区间递归地构建同样的树
• 把包含中心点的区间分成两个有序序列，一个按起始点排序，另一个按结束点排序

在搜索时，根据中心点的情况向左或向右查找。当你找到重叠的区间时，可以在你想检查的有序序列上使用二分查找（这不仅可以查找包含给定点的区间，还可以查找与给定区间相交或包含给定区间的区间）。

修改这个数据结构以返回特定值而不是找到的区间是很简单的。

---

不过，从上下文来看，我觉得你其实不需要提高查找的效率，可能更应该使用简单易读的解决方案，因为这样更容易维护，也更不容易出错。

不过，了解更高效的数据结构在未来可能会很有用。

Answer 2

最简单的方法可能就是写一个简短的函数：

def convert(n, difficulties=[0, 46, 91, 136, 201]):
    if n < difficulties[0]:
        raise ValueError
    for difficulty, end in enumerate(difficulties):
        if n < end:
            return difficulty
    else:
        return len(difficulties)

示例：

>>> convert(32)
1
>>> convert(68)
2
>>> convert(150)
4
>>> convert(250)
5

---

顺便提一下：在Python 3.x中，你可以把range用作字典的键，但在2.x中不能直接使用（因为range返回的是一个列表）。你可以这样做：

TIME_RATING_KEY = {tuple(range(0, 46)): 1, ...}

不过这也没什么太大帮助！