3

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

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

PS：

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

5 回答 5

4

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

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

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

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

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

于 2012-06-03T09:28:21.410 回答
2

数字有一个很好的属性，我认为可以在这里为您提供帮助：

对于一个给定的值为 KXXXX 的数a ，其中 K 是给定的，我们可以推断出 K0000 <= a < K9999。

使用这个属性，我们可以尝试构建一个在范围内的排列：

让我们举个例子：

范围 = [200, 250]

数字 = 122

首先，我们可以定义第一个数字必须是 2。我们有两个 2，所以到目前为止我们很好。

第二个数字必须介于 0 和 5 之间。我们有两个候选者，1 和 2。仍然不错。让我们检查第一个值 1：

任何数字在这里都很好，我们仍然有一个未使用的 2。我们找到了我们的排列 (212)，因此答案是Yes。

如果我们确实发现了与值 1 的矛盾，我们需要回溯并尝试值 2，依此类推。

如果没有一个解决方案是有效的，则返回No。

该算法可以使用回溯来实现，并且应该非常有效，因为您只有 2 个值来测试每个位置。该算法的复杂度为 2^l，其中 l 是元素的数量。

于 2012-06-03T09:44:18.193 回答
0

您可以尝试实现某种二进制搜索：

如果你的号码中有 6 个 1 和 4 个 2，那么首先你有间隔

[1111112222; 2222111111]

如果您的范围不与此间隔重叠，那么您就完成了。现在把这个区间分成中间，你得到

(1111112222 + 222211111) / 2

现在找到小于分割点的由 1 和 2 组成的最大数。（可能通过基于 1 和 2 以某种有效方式直接计算拆分或将 1 和 2 解释为二进制数的 0 和 1 来改进此步骤。也可以考虑采用这两个数字的几何平均值，因为候选人可能会更均匀地分布在左右两边。）

[编辑：我想我明白了：假设边界具有 pq 和 pr 的形式（即 p 是一个公共前缀），然后从 q 和 ra 对称字符串 s 构建，字符串的开头和结尾都是 1和中间的 2 并将 ps 作为分割点（因此从 1111112222 和 1122221111 开始，您将构建 111122222211，前缀为 p=11）。]

如果此数字包含在该范围内，则您已完成。

如果不是，请查看范围是高于还是低于并使用 [old lower bound;split] 或 [split;old upper bound] 重复。

于 2012-06-03T09:39:30.387 回答
0

假设给你的范围是：ABC 和 DEF（每个字符都是一个数字）。

Algorithm permutationExists(range_start, range_end, range_index, nos1, nos2)

     if (nos1>0 AND range_start[range_index] < 1 < range_end[range_index] and
          permutationExists(range_start, range_end, range_index+1, nos1-1, nos2))
               return true
     elif (nos2>0 AND range_start[range_index] < 2 < range_end[range_index] and
          permutationExists(range_start, range_end, range_index+1, nos1, nos2-1))
               return true
     else
               return false

我假设每个数字都是一系列数字。给定的数字表示为{numberOf1s, numberOf2s}。我试图在范围内拟合数字（前 1，然后是 2），如果不是，则程序返回错误。

PS：我可能真的错了。我不知道这种事情是否可以工作。我没有考虑太多，真的..

更新

我表达算法的方式是错误的。有一些更改需要在其中完成。这是一个工作代码（它适用于我的大多数测试用例）：http: //ideone.com/1aOa4

于 2012-06-03T09:54:11.497 回答
0

你真的只需要检查最多两个可能的排列。

假设您的输入数字仅包含数字 X 和 Y，其中 X<Y。在您的示例中，X=1 和 Y=2。 我会忽略所有你用完一个数字或另一个数字的特殊情况。

阶段 1：处理公共前缀。

令 A 为范围下限中的第一个数字，令 B 为范围上限中的第一个数字。如果 A<B，那么我们完成了第 1 阶段并进入第 2 阶段。

否则，A=B。如果 X=A=B，则使用 X 作为排列的第一个数字，并在下一个数字上重复阶段 1。如果 Y=A=B，则使用 Y 作为排列的第一个数字，并在下一个数字上重复阶段 1。

如果 X 和 Y 都不等于 A 和 B，则停止。答案是不。

第 2 阶段：使用通用前缀完成。

此时，A<B。如果 A<X<B，则使用 X 作为排列的第一个数字，并根据需要填写剩余的数字。答案是肯定的。（同样，如果 A<Y<B。）

否则，请检查以下四种情况。最多有两种情况需要实际工作。

  • 如果 A=X，则尝试使用 X 作为排列的第一个数字，然后是所有 Y，然后是其余的 X。换句话说，使排列的其余部分尽可能大。如果这个排列在范围内，那么答案是肯定的。 如果此排列不在范围内，则任何以 X 开头的排列都不会成功。
  • 如果 B=X，则尝试使用 X 作为排列的第一个数字，然后是其余的 X，然后是所有 Y。换句话说，使排列的其余部分尽可能小。如果这个排列在范围内，那么答案是肯定的。 如果此排列不在范围内，则任何以 X 开头的排列都不会成功。
  • 如果 A=Y 或 B=Y，则类似情况。

如果这四种情况都没有成功，那么答案是否定的。请注意，最多有一个 X 案例和最多一个 Y 案例可以匹配。

在这个解决方案中，我假设输入数字和范围内的两个数字都包含相同的位数。通过一些额外的工作，该方法可以扩展到位数不同的情况。

于 2012-06-03T15:02:35.817 回答