algorithm - 查找数字的任何排列是否在一个范围内

Question

我需要查找指定范围内是否存在数字的任何排列，我只需要返回是或否。

例如:Number = 122 和 Range = [200, 250]。答案是是，因为范围内存在 221。

附言:

1. 对于我手头的问题，要搜索的号码 只会有两个不同的数字(它只会包含 1 和 2， 例如:1112221121)。
2. 这不是一道作业题。这是在采访中被问到的。
3. 我建议的方法是找到给定数字的所有排列并检查。或者遍历范围并检查我们是否找到数字的任何排列。

Answer 1

检查每个排列太昂贵且没有必要。

首先，您需要将它们视为字符串，而不是数字，

将每个数字位置视为一个单独的变量。

考虑每个变量可以容纳的可能数字集如何受范围限制。每个数字/变量对要么 (a) 始终有效 (b) 始终无效；或 (c) 其有效性有条件地取决于特定的其他变量。

现在将这些依赖性和独立性建模为图形。由于情况 (c) 很少见，因此很容易在与 O(10N) = O(N) 成正比的时间内搜索