AlgoPressAppearance
0287-寻找重复数
https://leetcode.cn/problems/find-the-duplicate-number
给定一个包含n + 1 个整数的数组nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ，返回这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
示例 1：
输入：nums = [1,3,4,2,2]
输出：2
示例 2：
输入：nums = [3,1,3,4,2]
输出：3
提示：
- 1 <= n <= 10^5
- nums.length == n + 1
- 1 <= nums[i] <= n
- nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次
进阶：
- 如何证明 nums 中至少存在一个重复的数字?
- 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？
思路1 : 暴力法(超时)
暴力法，遍历两次，查询是否有重复的数字 因为复杂度为 O(n^2) 会超时
csharp
public class Solution {
public int FindDuplicate(int[] nums) {
for(int i=0; i<nums.Length - 1; i++){
for(int j = i+1; j<nums.Length; j++){
if(nums[i] == nums[j]){
return nums[j];
}
}
}
return -1;
}
}
思路2 : 哈希表
使用哈希表储存次数，这个方法同样没有使用到 [1..n] 这个特性
csharp
public class Solution{
public int FindDuplicate(int[] nums){
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i=0; i<nums.Length; i++){
if(!dict.ContainsKey(nums[i])){
dict.Add(nums[i],1);
}
else{
return nums[i];
}
}
return -1;
}
}
时间复杂度 O(n) 哈希表查找 O(1) 所以最终复杂度是 O(n) 空间复杂度 O(n)
进阶解法 : 二分查找
需要使用到 [1..n] 这个特性 我们先从 1..n，我们定义 count[i] 表示数组中小于等于i的数总和， 如果没有重复的数，那么有 count[i] = i 当出现重复的数字时： 我们取中间一个数 mid，当重复数字出现在 [1..mid] 中时，那么必然有 count[mid] > mid 反之重复数字出现在 (mid..n] 中 我们使用这个特性折半查找
csharp
class Solution{
public int FindDuplicate(int[] nums){
int left = 1;
int right = nums.Length - 1;
int ans = -1;
while(left <= right){
int mid = left + (right - left) / 2;
int count = 0;
for(int i = 0; i < nums.Length ; i++){
if( nums[i] <= mid){
count ++;
}
}
if(count <= mid){
left = mid + 1;
}
else {
right = mid - 1;
ans = mid;
}
}
return ans;
}
}
时间复杂度 O(nlogn)
进阶解法2 ： 二进制位运算
我们把每个数的二进制位数都统计出来，如果有一个重复的数字，那么他所在的位的1的个数就会大于原来的个数 如示例： 1,3,4,2,2 他们的二进制排列如下
| 1 | 3 | 4 | 2 | 2 | x | y | |
|---|---|---|---|---|---|---|---|
| 第 0 位 | 1 | 1 | 0 | 0 | 0 | 2 | 2 |
| 第 1 位 | 0 | 1 | 0 | 1 | 1 | 3 | 2 |
| 第 2 位 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
我们把 x > y 的位数出去来，就可以还原多出来的那个数字的二进制位，进而还原出原来的数字
有效性证明：如果只有2位重复数组，那么只会增加1的个数，其余不变
如果有3位或以上重复，那么会有缺失的数字
那么同样的位数多的1会增加，缺失的数组如果是0，那么不会受影响，如果是1，则他小于我们统计的常规个数，所以不影响最终判断。
csharp
class Solution{
public int FindDuplicate(int[] nums){
//定义32位数组，因为C#中int是32位的
//每一位单独计算
int ans = 0;
int bit_max = 31;
while (( nums.Length >> bit_max ) > 0) {
bit_max -= 1;
}
for(int bit = 0; bit <= bit_max; bit++){
int x = 0, y = 0;
for(int i=0; i<nums.Length; i++){
//这里是把1左移对应的位数
if( (nums[i] & (1 << bit)) != 0){
//统计位数
x+=1;
}
//然后从1统计到n
if(i>0 && ( (i & (1 << bit)) != 0 )){
y+=1;
}
}
if(x > y){
ans = ans | 1 << bit;
}
}
return ans;
}
}
进阶解法3 ：环
快慢指针法
csharp
class Solution{
public int FindDuplicate(int[] nums){
int slow = 0;
int fast = 0;
while(true){
slow = nums[slow];
fast = nums[nums[fast]];
if(slow == fast){
break;
}
}
fast = 0;
while(nums[slow] != nums[fast]){
slow = nums[slow];
fast = nums[fast];
}
return nums[slow];
}
}