时间戳

首页 > 解决方案 > 关于数组问题的问题（查找重复项）

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

问题描述

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

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
    }
}

标签： javaalgorithm

解决方案

这是一个有趣的算法，我尝试了这个来弄清楚发生了什么，在我尝试的示例中，我的值大于导致 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

推荐阅读