-1

我正在寻找一种算法来查找两个整数之间的数字列表，以使每个数字中的数字不重复？

例如，给定输入 2 和 12，答案将是除 11 之外的所有数字。天真的解决方案是遍历数字并检查是否有任何数字重复。但是，对于大数字，这种方法将花费大量时间。

我需要在给定的两个大数字之间找到此类数字的计数；我认为的另一种方法是采用大小为 10 的数组（a[10]），其中每个索引将存储某个数字的每个数字的频率。b/w 限制，如果我们得到一个 freq 超过 1 的索引，那么 no 将被丢弃。我将对限制之间的所有编号重复此操作，每次将数组“a”索引初始化为 0。但是这种方法对于大输入也将花费大量计算时间（例如当限制为 1 到 10^9 时） . 我需要一个更好的方法。

4

2 回答 2

4

我不会给你确切的解决方案，但会尝试给你一些关于如何处理类似问题的提示。

首先 - 每当您遇到类型问题时，请找到之间的数字计数，a并且b（几乎）总是更容易实现一个解决方案，该解决方案将为您提供(0, x]给定 x 区间的答案。例如，如果您想计算区间中的数字[a,b]并实现一个函数，该函数返回(0,x]所有非负 x 的区间答案（假设该函数是f），那么您可以计算[a,b]as的答案f(b) - f(a - 1)。相信我，这可以节省大量极端案例检查，并且通常实施起来更快。

话虽如此，请尝试思考如何计算区间中没有重复数字的数字(0,a]。我建议您分别计算具有固定位数的数字的答案。对于数字较少的数字，这非常简单 - 只需计算一个变化。对于位数等于我们的数字 a 的数字，这有点棘手。我相信使用动态编程来计算它们是最容易的。

希望这会有所帮助，并希望它不会太详细，以便您仍然需要自己解决问题。

于 2012-11-03T18:51:32.767 回答
0

您正在寻找一种算法来计算数字的排列。给定 m 位数的整数 A 和 n 位数的整数 B (m >= n)，您需要：

1. for i = m; i < n; i++
    if i < 10, choose i digits out of 10
    Permutate through digits of length i (if i=m, discard permutations that are less than A)

2. Permutate digits of length n, as long as result isn't larger than B.

选择和排列是组合运算，您可以轻松找到它们的数学公式（也可以使用递归版本），例如这里是描述排列的链接：http ://en.wikipedia.org/wiki/Permutation

复杂度将是 O((n+1)!)

于 2012-11-03T19:04:21.853 回答