leetcode 剑指 Offer 03. 数组中重复的数字

剑指 Offer 03. 数组中重复的数字

找出数组中重复的数字。

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

示例 1：

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

限制：

2 <= n <= 100000

解法一：计数排序

思路：

利用计数排序，在统计次数的时候判断出现次数是否大于1，如果大于1直接返回该数

 1 class Solution {
 2     public int findRepeatNumber(int[] nums) {
 3         int len = nums.length;
 4         // 计数排序,如果数量大于1则返回
 5         int[] counts = new int[len];
 6         for(int i = 0; i < len; i++){
 7             counts[nums[i]]++;
 8             if(counts[nums[i]] > 1){
 9                 return nums[i];
10             }
11         }
12         return -1;
13     }
14 }

leetcode 运行时间为2ms, 空间为45.9MB

复杂度分析：

时间复杂度：计数排序，但是不需要统计完，所以平均时间复杂度为O(n/2)

空间复杂度：需要创建一个和nums数组等大的数组，所以空间复杂度为O(n)

解法二：

思路来源：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/yuan-di-zhi-huan-shi-jian-kong-jian-100-by-derrick/

在元素不重复的情况下，但数组有序时，每个元素所在的位置和这个元素的值相等。所以我们遍历数组，把当前元素放到正确的位置，也就是以这个元素为下标的位置，把当前元素和他正确的位置的元素进行交换。重新安排位置的过程中，肯定就会有元素重复的情况。返回即可

 1 class Solution {
 2     public int findRepeatNumber(int[] nums) {
 3         int len = nums.length;
 4 
 5         for(int i = 0; i < len; i++){
 6             // 如果当前元素不在正确的位置
 7             if(nums[i] != i){
 8                 // 如果重复，直接返回
 9                 if(nums[i] == nums[nums[i]]){
10                     return nums[i];
11                 }
12                 // 把当前元素放到正确的位置
13                 int temp = nums[nums[i]];
14                 nums[nums[i]] = nums[i];
15                 nums[i] = temp;
16             }
17         }
18         return -1;
19     }
20 }

leetcode运行时间为1ms, 空间为46.3MB

复杂度分析：

时间复杂度：最多完整的遍历一次数组，平均复杂度为O(n/2)

空间复杂度：O(1)

解法三：利用HashSet

判断当前元素是否存在于HashSet,如果存在说明是重复元素，直接返回，否则把这个元素存入HashSet

 1 class Solution {
 2     public int findRepeatNumber(int[] nums) {
 3         int len = nums.length;
 4 
 5         HashSet<Integer> hs = new HashSet<Integer>();
 6         for(int num : nums){
 7             if(hs.contains(num)){
 8                 return num;
 9             }
10             hs.add(num);
11         }
12         return -1;
13     }
14 }

leetcode运行时间为10ms, 空间为47.6MB, 可以看到这个运行时间远大于上面两种方法，所以知道对HastSet虽然也是以hash函数来存取元素的，但是效率远低于直接操作数组。

复杂度分析：

时间复杂度：最多完整的遍历一次数组，平均复杂度为O(n/2)

空间复杂度：hashset中存储的元素个数，O(n)