跳至主要內容

03-数组中重复的数字

daipeng大约 3 分钟

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，重复的是2或者3，输出任意一个即可。

hashmap方法

我们可以用一个hashmap将数组的值和出现的次数保存起来，当遇到值出现的次数大于1时就是重复了，这种方法很简单。

Java的Set方法

我们可以使用集合set的本身能力进行判重处理。如果无法向set中添加元素，说明重复了。

public int findRepeatNumberV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;
    }

新建数组方法

我们仔细看下题目会注意到所有数字都在0到n-1的范围内这个条件，一般出现这种条件，我们考虑使用数组解决，因为这个条件限定了数字的范围，可以将数组的索引与数字对应起来。

我们可以初始化一个数组data[n]，然后扫描输入的数字，判断data[number]是否是0，假如不是0，说明发生了重复；假如是0，则将该data[number]自增1，表示已经出现该number了。

 public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length <= 1){
            return false;
        }
        int[] value = new int[length];
        for (int i = 0; i < length; i++) {
            int number = numbers[i];
            if (value[number] == 1) {
                duplication[0] = number;
                return true;
            }else{
                value[number]++;
            }
        }
        return false;
        
    }

数组原地交换比较方法

和 上面的 新建数组方法的考虑类似，所有数字都在0和n-1的范围内，这个范围和数组的索引范围是一致的，如果没有重复的数字，那么这两个范围应该是一一对应的，但因为有了重复数字，那么就会有多对一的关系。


public int findRepeatNumber(int[] nums) {
  
   if (nums == null || nums.length == 0) {
            return -1;
        }
        int idx = 0;
        int repeatNumber = -1;
        while (idx < nums.length) {
            int curNumber = nums[idx];
            if (curNumber == idx) { //如果当前的值与当前的索引一致，说明这个数字和索引是对应的，即number[x] == x这种情况，那么将idx自增即可，查看下一个数字。
                idx++;
            }else if (nums[curNumber] != curNumber) { //如果当前值与索引值不相同，并且当前值与nums[当前值]也不同，就进行交换，从而使得nums[当前值] == 当前值，这样就可以将nums[当前值]调整好
                nums[idx] = nums[curNumber];
                nums[curNumber] = curNumber;
            }else {
              //如果当前值与索引值不相同，并且当前值与nums[当前值]相同，说明发生了重复
                repeatNumber = curNumber;
                break;
            }
        }
        return repeatNumber;
}

我们梳理下代码是如何执行的

初始数组是

  1. idx=0，value=2 , 2不等于0，那么把nums[0]与nums[2]交换，这样可以保证nums[2]的索引和值是相等的，交换后数组为

  2. idx=0，value=1，1不等于0，那么把nums[0]与nums[1]交换，交换后数组为

  3. 重复比较，这次交换后为

  4. 因为前4个的索引和值都对应，那么会一直遍历到nums[4]，此时value=2，idx=4，不相等，需要将nums[4]和nums[2]进行交换，但在交换之前我们可以看到nums[2]已经是2了，说明重复了，此时就是查找到了重复的值，返回即可。

四种方法的分析

前三种方法类似，使用了额外的空间。

第四种方法直接操作了原数组，没有使用额外的空间。