java - 关于数组问题(查找重复项)的问题

Question

所以我一直在寻找一些资源来准备我的面试技巧。我对这个在数组中查找重复值的算法感到困惑，只是希望有人澄清这段代码中出现两点的地方。这两点是: 数组元素被限制在一个小于数组长度本身的 block 中，并且， 代码如何根据负值判断是否存在重复？

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 条件。

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

请注意，为了使该算法起作用，必须满足以下先决条件:

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