在O(1)空间和O(n)时间内确定大小为n、值在0到n-2范围内的数组中的所有重复项。

Question

给定大小为n的整数数组，它只能包含0到n-2范围内的值。 数组中可能有多个重复项。是否有一种方法可以在不修改数组的情况下，在O(n)时间和O(1)空间内确定所有可能的重复项？

这里有一个算法（链接），但它会修改数组。还有另一个算法（链接），但从我看来，它只能确定其中一个重复项。是否有一种方法可以确定所有重复的数字？

- Sean Durvasula

---

不，没有O（1）的空间限制。为了确定所有可能的重复项，您需要一个新数组，其大小高达N，以存储重复项（例如，N个相同元素或N/2对元素）。 - Mark Shevchenko

第二个链接描述了一个更简单的问题版本，并声称Donald Knuth花了24小时才解决。你确定你的更难的版本是正确的吗？ - jwg

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - David Eisenstat

Answer 1

如果数组中的数字是任意的，我认为没有比O(n^2)更少的方法来完成它。

然而，我会非常仔细地看待数据的限制，即可能的值必须从0到n-2中选择。这使您能够引入一种效率，虽然我不认为它会将您从O(n^2)恢复到O(n)，但至少可以大大提高算法的运行时间。

以下是它的工作原理。考虑从范围0..9中选择的十个数字：

0 1 2 3 4 5 6 7 8 9

现在介绍一个副本：

0 1 2 3 4 5 6 2 8 9

你需要注意的是，重复元素的引入导致在使用的数字集中出现了一个洞口 - 列表中不再有7。

实际上，每次引入重复值都会使得可能的值彻底消失，你可以利用这个事实来优化你的算法。关键在于不是为每个可能的数字搜索列表，而是利用每一次搜索来找到你应该寻找的下一个数字（比当前数字大的最小数字）。考虑以下包含13个元素的列表：

{0, 1, 1, 1, 2, 3, 0, 7, 9, 3, 9, 3, 9}

首先，我们搜索0。我们发现它是一个重复项，但我们还发现下一个可能的数字是1，因此我们记住它以备下一阶段使用。

接下来的几次迭代中，我们搜索1（重复项）和下一个是2，然后搜索2（唯一项）和下一个是3。

但这里变得有趣了。当我们搜索3（重复项）时，我们发现下一个可能的数字实际上是7，因此我们完全可以跳过4、5和6。当然，我们也会因同样的原因跳过8（在搜索7时，我们发现下一个是9）。

当我们搜索9时，没有下一个可能的术语，因此我们可以在那个点停止。

在伪代码¹中，类似于以下内容：

list = [0,1,1,1,2,3,0,7,9,3,9,3,9]
n = len(list)

# Initial search term and begin loop for each term.

currN = 0
while currN <= n - 2:
    print ("Checking for %d"%(currN))

    # Next search term, initially beyond max, and dupe detector.

    nextN = n
    count = 0

    # Check every list value.

    for val in list:
        # Count occurrences.

        if val == currN:
            count += 1

        # Update next search term if needed. If no value
        #   between curr and n, nextN will remain at n
        #   and loop will exit.

        if val > currN and val < nextN:
            nextN = val

    # Inform if duplicated and move to next search term.

    if count > 1:
        print ("%d is duplicated"%(currN))

    currN = nextN

---

如果你想要更高的性能，那么还有另一种可能的优化方案。目前，你在每次迭代中都会检查列表中的每个值，但这并不是必要的。

例如，一旦你检查过 0，再次检查第一个索引 {0} 就没有意义了，因为它永远不会再影响结果。

同样地，一旦你检查过 1，你就不需要再次访问前四个元素 {0, 1, 1, 1} 了。

因此，可以通过记住不仅是下一个可能的搜索项，而且还有可能找到它的最早时间点，以便后续迭代在搜索时处理较少的元素来获得优势。

实现该方法的方式是从一个变量位置开始搜索，最初位于列表的开头。然而，在每次迭代中，你将更新此位置为列表中第一个大于当前正在处理的搜索项的项的位置。

---

如上所述，我不认为这些建议会给你O(n)，但肯定比朴素的方法好。对于没有重复项的情况（例如{1, 2, 3, 4}），操作次数将接近n * n，而对于列表中只有一个重复值的情况（例如{1, 1, 1, 1}），操作次数将降至约n。

重复项越多，运行时间就越好。

---

¹ ...这看起来非常像Python3代码 :-)

- paxdiablo