logo标签列表

在O(n)时间和常数空间内查找重复项

algorithm
7
你为什么接受了错误的答案？（不是O(1)空间） - TT_ stands with Russia
4个回答
24

计算两个和：sum和square sum。

以你的示例为例：

sum = 1+99+3...+100

sq_sum = 1^2+99^2+3^2+...+100^2
假设序列中用 y 替换了 x。
sum = n(n+1)/2 -y+x.
sq_sum = n(n+1)(2n+1)/6 -x^2 +y^2

现在，求解x和y。

常数空间和O(n)时间。

如何求解x和y

从方程式中：

x = sum - n(n+1)/2 +y

将这个代入第二个方程：

sq_sum = n(n+1)(2n+1)/6 -(sum - n(n+1)/2 +y)^2 +y^2
注意y^2被消除了，你只剩下一个只有一个未知数y的线性方程。解决它！
2
这个回答有2个踩和没有评论。请解释一下这里的错误，以便OP可以反驳或修改，其他人也能理解（可能存在的）问题。 - PengOne
你如何求解 x 和 y 的值？ - WisaF
真的需要平方和吗？如果数组长度为101且有100个唯一值，则将这100个唯一值相加并得到5050，假设总和返回为5149，则立即知道99被重复了，当存在多个重复项时，此方法不起作用，但问题仅提到了一个值重复一次。 - Seph
@Seph 数组长度为100。一个数字被重复，一个数字被省略。因此有两个未知数，需要两个方程式。 - Nick Barnes
为什么会有人踩一个正确的答案呢？ - TT_ stands with Russia
sum和sq_sum所需的空间取决于输入大小，即不是恒定空间。 - Justin Bell
4
新方法。设m是缺失的数字，r是重复的数字。经过数组一次，设X是对数组条目和索引1到n进行异或处理的结果。那么X = m XOR r。特别地，它不是0。让b是X中任何非零位（您只需要选择一个，因为X不是0）。通过数组时，让Y是对数组条目和索引1到n进行异或处理的结果，在其中位b为0，并且让Z是对数组条目和索引1到n进行异或处理的结果，在其中位b为1。然后，Y和Z分别保存m和r，所以唯一剩下的就是进行最后一次遍历，以确定它们是否在数组中。
总空间：4（如果您将X用于b，则为3）。
总时间：7次遍历（如果您同时对索引和数组进行处理，并在同一时间计算Y和Z，则为3）。
因此，空间复杂度为O（1），时间复杂度为O（n）。
你确定吗？在第一步中，slow 是 n+1。所以 array[slow] 会返回错误或垃圾值，对吧？ - ElKamina
1
我仍然认为这不会起作用。考虑存在多个循环的情况。或者考虑一个数组[n]=n的情况。 - ElKamina
那么对于X的每个非零位，您需要额外进行一次遍历，对吗？在这种情况下，您的解决方案时间复杂度为O（nlogn）。我不太确定这个事实，但请告诉我。 - ElKamina
@ElKamina 不，你只需要对你最喜欢的非零位进行一次遍历。你不必为每个非零位都这样做。它适用于任何非零位。 - PengOne
1
X的大小是否取决于n？如果是，那么它不是O(1)空间。 - TT_ stands with Russia
1

我们可以用O(n)的时间复杂度和常量空间来完成：

  1. 对于每个元素，计算 index = Math.abs(a[i]) - 1
  2. 检查 index 处的值
    • 如果它是正数，乘以-1，即使它变成负数。
    • 如果它是负数，则返回(index+1)作为答案，因为这意味着我们之前已经看到了这个索引。

""

static int findDup(int[] a){
    for(int i=0;i<a.length;i++){
        int index = Math.abs(a[i]) - 1;
        if(a[index] < 0)
            return index+1;
        else
            a[index] = -1 * a[index];
    }
    return -1;
}
10
你正在为输入中的每个元素存储一条信息（可能性），这不是常量空间。 - Nick Barnes
6
你仍然在使用线性的空间构建你的解决方案。如果你的输入集是不可变的、或者不支持随机访问、或者不支持有符号整数，那么你需要自己创建这个数组。 - Nick Barnes
9
这些限制条件（可修改的带有常量时间随机访问的输入）在问题中并没有被明确说明，因此假设它们有点牵强。但无论如何，这仍然不能算作一个常量空间算法。问题不在于需要分配多少字节内存；而是需要记录多少个信息片段。 - Nick Barnes
1
@Manan 但是你仍然在存储一些东西。你的算法基本上是桶排序。在这种情况下，你的桶是输入数组中空闲的符号位。但它仍然是一个线性空间算法。 - Nick Barnes
2
@Manan 这行代码 a[index] = -1 * a[index]; 覆盖了输入。这就是为什么人们说这个解决方案不是常数空间的原因。 - PengOne
显示剩余16条评论
-1

计算所有整数的总和 计算 int p = sum % 100 100 - p 就是答案

1
这只会给你缺失数字和重复数字之间的差异，但不足以识别它们中的任何一个。你有两个未知数，需要两个方程式。请参见上面ElKamina的答案。 - Nick Barnes
1
例子：1，99，3，4...100。现在求和 % 100 的结果是 98。100-98 等于 2 :) - topcoder
1
@topcoder 我得到 1+99+3+4+...+100 % 100 = 47。 - PengOne
1
@NickBarnes 1到100的求和模100不等于0。为什么大家都认为它是呢？1+2+...+100=5050！ - PengOne
@PengOne 哎呀，你说得对...忘记除以2了 :) - Nick Barnes
显示剩余3条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接