c - 查找 2 个整数之间数字不重复的数字计数的算法

Question

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

例如，输入 2 和 12，答案将是除 11 之外的所有数字。最简单的解决方案是迭代这些数字并检查是否有任何数字重复。但是，对于大量数据，这种方法将花费大量时间。

<小时/>

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

Answer 1

我不会给您确切的解决方案，但会尝试为您提供一些如何解决类似问题的提示。

首先 - 每当您遇到此类问题时，查找 a 和 b 之间的数字计数(几乎)总是更容易实现以下解决方案:将为您提供给定 x 的区间 (0, x] 的答案。例如，如果您想计算区间 [a,b] 中的数字，并且您实现一个函数，返回所有非负 x 的区间 (0,x] 的答案(假设该函数是 f)，然后您可以计算答案对于 [a,b] 为 f(b) - f(a - 1)。相信我，这可以节省大量的极端情况检查，并且通常实现速度更快.

话虽如此，请尝试思考如何计算间隔 (0,a] 中没有重复数字的数字。我建议您计算以下答案:分别具有固定位数的数字。对于位数少于 a 的数字，这非常简单 - 只需计算变体。对于位数等于我们的数字 a 的数字，这有点棘手。我相信它使用 dynamic programming 来计算它们是最简单的。

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