LeetCode – 寻找重复数

• 2019 年 10 月 4 日
• 筆記

LeetCode第287题，难度中等。

原题地址：https://leetcode-cn.com/problems/find-the-duplicate-number/

题目描述：

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:  输入: [1,3,4,2,2]  输出: 2    示例 2:  输入: [3,1,3,4,2]  输出: 3

说明：

• 不能更改原数组（假设数组是只读的）。
• 只能使用额外的 O(1) 的空间。
• 时间复杂度小于 O(n2) 。
• 数组中只有一个重复的数字，但它可能不止重复出现一次。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/find-the-duplicate-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

这个题目要求只能使用额外的O(1)的空间，时间复杂度小于O(n^2)，所以不能使用位图的方式。但是存在其他的多种方式。

第一种：我认为是最简单粗暴的一种方式，时间复杂度最差情况下刚好是O(n^2)，也就是循环遍历数组，分别比对每个元素，在数组中是否存在相同的元素，如果存在相同的元素，则立即返回。

第二种：先排序，排序之后，相同的元素必然处于相邻的位置，那么直接遍历一次即可（当然这个方法存在利用额外的空间，空间复杂度可能不是O(1)）

第三种：利用Set集合，不过也很明显使用了额外空间。

中文官网题解：

https://leetcode-cn.com/problems/find-the-duplicate-number/solution/

个人题解：

public class Solution {      public int findDuplicate(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 0;      }  }

结果：

这个是简单粗暴的方式的执行结果，可以很明显看到快的速度可以达到近乎0ms。