关于数组问题的问题（查找重复项）

Question

所以我一直在寻找一些资料来准备我的面试技巧。我对这一算法感到困惑，在数组中找到重复的值，只是希望有人澄清这个代码中的两个点出现的位置。这两点是：数组元素被限制在一个小于数组长度本身的块中，代码如何确定是否存在基于负值的重复项？

public class CheckDuplicates {
    public void hasDuplicates(int[] arrA){
        for(int i = 0; i < arrA.length; i++){
            if(arrA[Math.abs(arrA[i])] < 0){
                System.out.println("Array has duplicates: " + Math.abs(arrA[i]));

            } else{
                arrA[Math.abs(arrA[i])] = arrA[Math.abs(arrA[i])] * -1;
            }
        }
    }

    public static void main(String[] args) {
        int a[] = {1,6,1,1,2,2,5,6, 8, 9, 6, 6, 6, 6, 10, 10};
        new CheckDuplicates().hasDuplicates(a);
        // TODO Auto-generated method stub
    }
}

Answer 1

这是一个有趣的算法，我试着弄清楚发生了什么，在我尝试的例子中，我的值大于导致java.lang.ArrayIndexOutOfBoundsException的数组长度。然后我在你的例子中意识到所有数组值都小于数组本身的长度。

这样做的原因是因为算法使用数组值本身作为索引来在数组中标记以确定是否存在重复。当它遍历每个元素时，它将元素的值设置为该元素值的索引值为负，因此如果它存在相同的值则迭代它并检查该索引是否曾被设置为负值然后我们知道找到了副本。

如果在每次迭代后打印出数组本身，这一点就会变得更加明显：

[1, -6, 1, 1, 2, 2, 5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 1
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 1
[1, -6, 1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 2
[1, -6, -1, 1, 2, 2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, 8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, 9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
Array has duplicates: 6
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, 6, 6, 6, 6, 10, 10]
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, -6, 6, 6, 6, 10, 10]
Array has duplicates: 10
[1, -6, -1, 1, 2, -2, -5, 6, -8, -9, -6, 6, 6, 6, 10, 10]

从这里我们可以看到第一次迭代（i = 0）数组元素的值是1.索引1处的数组的值= 6.这个值> 0，所以它进入else条件并设置值在这个指数为-6。第二次迭代它在取索引6处的值时做同样的事情（注意Math.abs用于防止负索引）并将值5设置为-5，然后在第二次迭代中再次将其设置为else条件。

现在在第三次迭代中，数组[2]的值= 1，其值为-6。由于这是否定的，我们知道我们必须事先看到这个值，因为它将值设置为负数，因此必须是重复的。

请注意，为了使此算法有效，必须满足以下前提条件：

1) The values of the array elements must be [0,n) where n = the length of the array

Answer 2

由于所有元素都小于长度，因此可以使用元素的值作为索引。通过将值设置为负值，它被标记为已被读取，因此如果找到负值，则意味着该元素已被读取为另一个索引，并且由于该索引对应于与当前索引相同的值，请记住它们是使用元素的值作为索引，我们有一个重复。

对于示例中的数组，索引1首先设置为-6，对于i = 0，然后当i为2时，值为1，对于索引1，我们有-6，因此我们在索引0和2处有重复