arrays - 计算不同的数组条目 [不添加内存也不更改数组]

Question

任务是计算给定数组的唯一数字。我在 SO 上看到了很多类似的问题，但是这里我们有额外的要求，这些要求在其他问题中没有说明:

• > 允许的额外内存量为 O(1)
• 数组的变化是 禁止

我能够编写符合给定约束条件的二次算法。但我一直在想，在这样的问题上是否可以做得更好？感谢您的宝贵时间。
O(n^2) 的算法

def count(a):
    unique = len(a)
    ind = 0
    while ind < len(a):
        x = a[ind]
        i = ind+1
        while i < len(a):
            if a[i] == x:
                unique -= 1
                break
            i += 1
        ind += 1

    print("Total uniques: ", unique)

Answer 1

这与 Cracking the Coding Interview 第 1 章(数组和字符串)中的后续问题非常相似:

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

答案(对后续问题)是，如果您不能对数组进行任何假设(即，它没有排序，您不知道它的大小等)，那么就没有算法比你展示的要好。

话虽如此，您可能会考虑稍微放宽限制，让它变得更有趣。例如，如果数组大小有上限，则可以使用位向量来跟踪在遍历数组时读取的值，尽管严格来说这不是 O(1) 关于内存使用的解决方案(有人可能会争辩说，通过知道最大数组大小，内存使用是恒定的，因此 O(1)，但这有点作弊).同样，如果数组已排序，您也可以在 O(n) 中解决它，方法是一次遍历每个元素并检查其相邻元素是否为不同的数字。