在O(n)和常数空间中找到重复

Question

可能重复:
简单的面试问题变得更难:给定数字1..100,找到丢失的数字
在线性时间和恒定空间中找到数组中缺失和重复的元素

我在一个论坛上看到了一个有趣的问题.

你有100个元素,从1到100,但是由于错误,其中一个数字重复另一个重复自己.例如1,99,3,...,99,100数组不是排序格式,如何找到重复数？

我知道哈希可以做O(n)时间和O(n)空间,我需要O(1)空间.

Answer 1

计算两个总和:和和平方和.

在你的例子中:

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.解决这个问题!

Answer 2

我们可以在 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;
}