乐趣区

关于算法:剑指offer-找出数组中重复的数字

jiezi

题目形容：

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范畴内。数组中某些数字是反复的，但不晓得有几个数字反复了，也不晓得每个数字反复了几次。请找出数组中任意一个反复的数字。

示例 1：

输出：[2, 3, 1, 0, 2, 5, 3]
输入：2 或 3

限度：

2 <= n <= 100000

计划一：暴力求解 “

暴力求解的思路十分的间接：

  • 遍历数组中的每个元素，而后在剩下的元素中寻找是否存在雷同的元素

代码如下：

public int findRepeatNumber(int[] nums) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[i] == nums[j]) {return nums[i];
            }
        }
    }
    return -1;
}

以上算法实现的复杂度剖析：

  • 工夫复杂度是 O(n^2)
  • 空间复杂度是 O(1)

仔细的应该会发现这道题目形容的最初对 n 做了一个限度，也就是：2 <= n <= 100000
那就是说，数据规模 n 有可能是 10 万级别的，如果工夫复杂度是 O(n^2) 的话，那么数据规模就会变成 10 万的平方了，这个级别就高了，所以下面的代码的性能是十分差的。接下来咱们来优化。

计划二：哈希查找

在暴力解法中，咱们先遍历每一个元素，而后再从其余的元素中查找这个元素是否存在，其实这里要的就是能高效的判断一个元素是否曾经存在，咱们能够应用哈希表，因为哈希表判断是否存在的工夫复杂度是 O(1)。

应用哈希表后的算法步骤是：

先初始化一个哈希表 (HashSet)
而后遍历每一个元素，别离对每一个元素做如下的解决：
先判断哈希表中是否存在这个元素
如果存在的话，则阐明这个元素反复，则间接返回
否则，将这个元素退出到哈希表中，不便后续的判重
代码如下：

public int findRepeatNumber(int[] nums) {
    // 1. 初始化一个哈希表
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {
        // 2. 判断以后元素是否曾经存在
        if (set.contains(nums[i])) {
            // 如果存在，则间接返回
            return nums[i];
        }
​
        // 否则的话，将以后元素放入到哈希表中，不便后续的查找判重
        set.add(nums[i]);
    }
    return -1;
}

以上算法实现的复杂度剖析：

  • 工夫复杂度是 O(n)
  • 空间复杂度是 O(n)

工夫复杂度 O(n)，对于数据规模 10 万级别的话，运行速度是能够承受的。然而这里的空间复杂度则变为 O(n)，因为哈希表须要申请额定的 n 个空间，这里用到的是典型的 空间换工夫的思维

计划三：数组代替哈希表

在题目中，有一个信息，咱们须要留神下，那就是数组中每个元素的大小在 0 ~ n – 1 的范畴内。利用这个信息，咱们就能够应用数组代替下面计划二的哈希表，次要的思路是：

定义一个长度为 n 的数组 bucket，而后将所有的元素初始化为 -1
在查找解决的时候，应用原数组的元素作为 bucket 的下标，原数组元素对应的下标作为 bucket 的元素值。
咱们间接看代码：

public int findRepeatNumber(int[] nums) {
    // 1. 初始化一个数组
    int[] bucket = new int[nums.length];
    Arrays.fill(bucket, -1);
​
    for (int i = 0; i < nums.length; i++) {
        // 2. 判断以后元素是否曾经存在
        if (bucket[nums[i]] != -1) {
            // 如果存在，则间接返回
            return nums[i];
        }
​
        // 否则的话，将以后元素作为索引，以后元素的下标作为值，填入数组中，// 不便后续的查找判重
        bucket[nums[i]] = i;
    }
    return -1;
}

以上算法实现的复杂度剖析：

工夫复杂度是 O(n)
空间复杂度是 O(n)
能够看出，工夫复杂度和空间复杂度都是和用哈希表的解决方案是一样的。然而应用数组相对会有性能的进步，次要体现在如下的两个方面：

哈希表 (HashSet) 底层是应用数组 + 链表或者红黑树组成的，而且它的数组也是用不满的，有加载因子的。所以应用数组来代替哈希表，能节俭空间
哈希表在判重的时候须要通过哈希计算，还可能存在哈希抵触的状况，而应用数组则能够间接计算失去 index 的内存地位，所以应用数组拜访性能更好。

计划四：最优解法

上面算法的次要思维是把每个数放到对应的地位上，即让 nums[i] = i。

public int findRepeatNumber(int[] nums) {for (int i = 0; i < nums.length; i++) {while (i != nums[i]) {
​
            if (nums[i] == nums[nums[i]]) {return nums[i];
            }
​
            // 替换
            int tmp = nums[nums[i]];
            nums[nums[i]] = nums[i];
            nums[i] = tmp;
        }
    }
    
    return -1;
}

以上算法实现的复杂度剖析：

  • 工夫复杂度是 O(n)
  • 空间复杂度是 O(1)

能够看出，咱们利用这种办法，空间复杂度降到了 O(1) 了。

退出移动版