By Long Luo
这篇文章是 287. 寻找重复数 的题解。
目前这道题,经过自己摸索和参考 官方题解: 寻找重复数 ,目前发现了9 种方法。
这些方法可以分为以下几类:
需要额外空间,需要修改原始数组 O ( l o g n ) O(logn) O ( l o g n ) space
排序 - O ( n l o g n ) O(nlogn) O ( n l o g n ) time
需要额外空间,不修改原始数组 O ( n ) O(n) O ( n ) space
计数法 - O ( n ) O(n) O ( n ) time
Set - O ( n ) O(n) O ( n ) time
不需要额外空间,需要修改原始数组 O ( 1 ) O(1) O ( 1 ) space
标记法 - O ( n ) O(n) O ( n ) time
索引排序 - O ( n ) O(n) O ( n ) time
不需要额外空间,不修改原始数组 O ( 1 ) O(1) O ( 1 ) space
暴力 - O ( n 2 ) O(n^2) O ( n 2 ) time
二分搜索 - O ( n l o g n ) O(nlogn) O ( n l o g n ) time
位运算 - O(nlogn) time
双指针 - O ( n ) O(n) O ( n ) time
因为题目要求:
必须不修改 数组 nums \textit{nums} nums ;
只用常量级 O ( 1 ) O(1) O ( 1 ) 的额外空间。
因此我们先从需要修改数组的方案开始,下面我们就来一一分析:
需要额外空间,需要修改原始数组
方法一:排序
先对数组进行排序,然后遍历数组,如果出现重复数字既是答案。
1 2 3 4 5 6 7 8 9 10 11 12 public static int findDuplicate_sort (int [] nums) { Arrays.sort(nums); int len = nums.length; for (int i = 1 ; i < len; i++) { if (nums[i] == nums[i - 1 ]) { return nums[i]; } } return len; }
复杂度分析
时间复杂度:O ( n l o g n + n ) O(nlogn + n) O ( n l o g n + n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度,O ( l o g n ) O(logn) O ( l o g n ) 排序复杂度,总时间复杂度为 O ( n l o g n + n ) O(nlogn + n) O ( n l o g n + n ) 。
空间复杂度:O ( l o g n ) O(logn) O ( l o g n ) ,排序需要使用 O ( l o g n ) O(logn) O ( l o g n ) 空间。
需要额外空间,不修改原始数组
方法二:计数法
因为数组元素值的范围是 [ 1 , n ] [1, n] [ 1 , n ] 之间,那么可以使用一个数组来记录数字出现次数,次数大于 1 1 1 即为答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 public static int findDuplicate_count (int [] nums) { int len = nums.length; int [] cnt = new int [len + 1 ]; for (int i = 0 ; i < len; i++) { cnt[nums[i]]++; if (cnt[nums[i]] > 1 ) { return nums[i]; } } return len; }
复杂度分析
时间复杂度:O ( n ) O(n) O ( n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( n ) O(n) O ( n ) ,需要新建一个长度为 n n n 的数组。
方法三:HashSet
同方法二,这里使用HashSet
来记录数组元素。
1 2 3 4 5 6 7 8 9 10 11 12 public static int findDuplicate_set (int [] nums) { Set<Integer> set = new HashSet <>(); int len = nums.length; for (int i = 0 ; i < len; i++) { if (!set.add(nums[i])) { return nums[i]; } } return len; }
复杂度分析
时间复杂度:O ( n ) O(n) O ( n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( n ) O(n) O ( n ) 。
不需要额外空间,需要修改原始数组
方法四:标记法
标记法的思想和计数法是一致的,但这个方法比计数法,Set \texttt{Set} Set 更为巧妙。
考虑到数组元素值的范围是 [ 1 , n ] [1, n] [ 1 , n ] ,但数组长度为 n + 1 n + 1 n + 1 ,那么很显然在遍历数组的时候,我们将数组的值变为其对应的负数,那么再次遇到负数就得到了答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 public static int findDuplicate_mark (int [] nums) { int len = nums.length; for (int num : nums) { int idx = Math.abs(num); if (nums[idx] < 0 ) { return idx; } nums[idx] = -nums[idx]; } return len; }
复杂度分析
时间复杂度:O ( n ) O(n) O ( n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法五:索引排序
索引排序是更难 想到的方法。
数组排序之后,每个数组元素的值是其索引值 i n d e x + 1 index + 1 i n d e x + 1 ,那么就可以进行如此操作:
如果 nums [ i ] = = i + 1 \textit{nums}[i] == i + 1 nums [ i ] = = i + 1 ,说明已经排好序了,那么跳过,i + + i++ i + + ;
如果 nums [ i ] = = nums [ nums [ i ] − 1 ] \textit{nums}[i] == \textit{nums}[\textit{nums}[i] - 1] nums [ i ] = = nums [ nums [ i ] − 1 ] ,说明在正确的索引已经有一个值了,那么这个值就是重复的元素;
上述均不满足,交换 nums [ i ] \textit{nums}[i] nums [ i ] 和 nums [ nums [ i ] − 1 ] \textit{nums}[\textit{nums}[i] - 1] nums [ nums [ i ] − 1 ] 的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public static int findDuplicate_index_sort (int [] nums) { int len = nums.length; for (int i = 0 ; i < len; ) { int n = nums[i]; if (n == i + 1 ) { i++; } else if (n == nums[n - 1 ]) { return n; } else { nums[i] = nums[n - 1 ]; nums[n - 1 ] = n; } } return 0 ; }
复杂度分析
时间复杂度:O ( n ) O(n) O ( n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
不需要额外空间,不修改原始数组
方法六:暴力2重循环
如果不允许额外空间,不允许修改原始数组,大多数人反而不会想到这个方法。
这个方法会超时 。
1 2 3 4 5 6 7 8 9 10 11 12 13 public static int findDuplicate_2loops (int [] nums) { int len = nums.length; for (int i = 0 ; i < len; i++) { for (int j = i + 1 ; j < len; j++) { if (nums[i] == nums[j]) { return nums[i]; } } } return len; }
复杂度分析
时间复杂度:O ( n 2 ) O(n^2) O ( n 2 ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法七:二分搜索
这里感谢大神 @liweiwei1419 的 详细题解 ,大家可以参考他的详细题解进行理解。
二分搜索是用来在有序数组 里查找某个特定的值,但是这个数组并不是有序的,咋一看不适合使用二分搜索算法。
因为题目中规定了数组里元素大小在 [ 1 , n ] [1, n] [ 1 , n ] 之间,而在 [ 1 , n ] [1, n] [ 1 , n ] 之间找一个整数,并不是在输入数组中查找某个整数,所以这道题可以使用二分查找。
二分查找的思路是先猜一个数(在有效范围 [ left , right ] [\textit{left}, \textit{right}] [ left , right ] 里位于中间的数 mid \textit{mid} mid ),那么这个中间数和哪个数进行比较呢?
如果目标数 target \textit{target} target 小于 mid \textit{mid} mid ,那么统计原始数组,小于等于 mid \textit{mid} mid 的元素的个数 cnt \textit{cnt} cnt ,c n t > m i d cnt \gt mid c n t > m i d ,反之 c n t ≤ m i d cnt \leq mid c n t ≤ m i d 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public static int findDuplicate_bs (int [] nums) { int len = nums.length; int low = 1 ; int high = len - 1 ; while (low < high) { int mid = low + (high - low) / 2 ; int cnt = 0 ; for (int i = 0 ; i < len; i++) { if (nums[i] <= mid) { cnt++; } } if (cnt <= mid) { low = mid + 1 ; } else { high = mid; } } return low; }
复杂度分析
时间复杂度:O ( n l o g n ) O(nlogn) O ( n l o g n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。二分查找最多需要二分 O ( l o g n ) O(logn) O ( l o g n ) 次,每次判断的时候需要 O ( n ) O(n) O ( n ) 遍历 nums \textit{nums} nums 数组求解小于等于 mid \textit{mid} mid 的数的个数,因此总时间复杂度为 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
方法八:位运算
具体证明及讲解可以参 @LeetCode-Solution 官方题解 。
简单来说,把数字转为二进制,那么其实只需要关注 1 1 1 的个数及位数。具体到第 i i i 位,我们统计 nums \textit{nums} nums 数组中二进制展开后第 i i i 位为 1 1 1 的数为 x x x 个,数字 [ 1 , n ] [1,n] [ 1 , n ] 这 n n n 个数二进制展开后第 i i i 位为 1 1 1 的数有 y y y 个,那么很显然只有 x > y x > y x > y 的情况下,重复的数的第 i i i 位为 1 1 1 。
分别把 [ 1 , n ] [1, n] [ 1 , n ] 和数组数字的所有位为 1 1 1 统计出来,然后按位还原,即可得到这个重复的数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public static int findDuplicate_bit (int [] nums) { int n = nums.length; int ans = 0 ; int bit_max = 31 ; while (((n - 1 ) >> bit_max) == 0 ) { bit_max -= 1 ; } for (int bit = 0 ; bit <= bit_max; ++bit) { int x = 0 , y = 0 ; for (int i = 0 ; i < n; ++i) { if ((nums[i] & (1 << bit)) != 0 ) { x += 1 ; } if (i >= 1 && ((i & (1 << bit)) != 0 )) { y += 1 ; } } if (x > y) { ans |= 1 << bit; } } return ans; }
复杂度分析
方法九:双指针
具体讲解可以参考 官方题解 @kirsche 的题解 287.寻找重复数 。
简单来说,因为数组数字在 [ 1 , n ] [1, n] [ 1 , n ] ,而数组索引值 [ 0 , n ] [0, n] [ 0 , n ] ,那么数组就可以构成一个环形链表 ,我们可以使用 nums [ nums [ i ] ] \textit{nums}[\textit{nums}[i]] nums [ nums [ i ] ] 来表示 nums [ i ] \textit{nums}[i] nums [ i ] .
那么问题就转化成了 142. 环形链表 II ,这里不多解释。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public static int findDuplicate_fastSlow (int [] nums) { int slow = 0 ; int fast = 0 ; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); slow = 0 ; while (slow != fast) { slow = nums[slow]; fast = nums[fast]; } return slow; }
复杂度分析
时间复杂度:O ( n ) O(n) O ( n ) ,其中 n n n 为 nums \textit{nums} nums 数组的长度。
空间复杂度:O ( 1 ) O(1) O ( 1 ) 。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions . 😉😃💗