algorithm - 不同的数字计数

Question

是否可以在恒定时间内计算一个数字中的不同数字O(1)？

假设n=1519输出应该是3因为有3不同的数字(1,5,9)。

我已经O(N)及时完成了，但有人知道如何及时找到它O(1)吗？

Answer 1

我假设N是 的位数n。如果 的大小n是无限的，则一般不能在 O(1) 时间内完成。

考虑一下这个数字n=11111...111，有 2 万亿位数字。如果我将其中一个数字从 a 切换1到 a 2，如果不以某种方式查看每个数字，就无法发现这一点。因此处理一个有 2 万亿位数字的数字必须至少进行（大约）2 万亿次操作，一般来说，一个有数字的N数字必须N至少进行（大约）操作。

然而，对于几乎所有的数字，简单的O(N)算法很快就完成了，因为你可以在达到 10 个不同的数字时立即停止。几乎所有足够长的数字都包含 10 位数字：例如，在查看前 100 位数字后，不以答案“10”结尾的概率约为 0.00027，而在前 1000 位数字之后，它约为 1.7e-45。但不幸的是，有一些奇怪的情况会造成最坏的情况O(N)。

Answer 2

在看到有人真的对这个问题发表了认真的答案之后，我宁愿在这里重复我自己的作弊，这是@SimonNickerson描述的答案的一个特例：

O(1) 是不可能的，除非你在基数 2 上，因为这样，除了 0 之外的每个数字都有 1 和 0，因此我的“解决方案”不仅适用于整数......

编辑

2^k - 1 怎么样？不都是1吗？

讨厌！是的...我应该知道，当某些事情看起来如此简单时，它以某种方式存在缺陷...如果我涵盖了所有 0 的情况，我也应该涵盖了所有 1 的情况。

幸运的是，可以很快地测试这种情况（如果加法和按位与被认为是 O(1) 操作）：如果 x 是要测试的数字，则以这种方式计算 y：y=(x+1) AND x。如果y=0，那么x=2^k - 1。因为这是唯一需要通过加法翻转所有位的情况。当然，这是相当有缺陷的，因为位长度超过了总线宽度，按位运算符不再是 O(1)，而是 O(N)。

同时，我认为它可以降低到 O(logN)，方法是将数字分解为总线宽度大小的块，然后将相邻的块与运算并在一起，重复直到只剩下一个：如果里面没有 0测试的数字，最后一个也将满1s...

EDIT2：我错了......这仍然是O（N）。