AlgoPressAppearance
03-数组中重复的数字
题目描述
https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
思路分析
常规解法，开辟一个字典Dict，保存已访问过的数字，如果存在，则说明有重复数组，否则就加入字典，循环到结束 时间复杂度 O(n)，此方法需要额外开辟一个字典存储空间
数组下标对应解法
注意到这里所有数字都在 0～n-1 的范围内，说明按照下标把数字都排列后，每个数字和下标应该是一一对应的，如果出现了不对应，说明有重复数字了 注意：这个方法会修改原数组
实现代码
- 常规解法
csharp
public class Solution {
public int FindRepeatNumber(int[] nums) {
Dictionary<int,int> dict = new Dictionary<int,int>();
for(int i = 0; i < nums.Length; i++){
if(dict.ContainsKey(nums[i])){
return nums[i];
}
else{
dict.Add(nums[i],nums[i]);
}
}
return -1;
}
}
- 数据下标对应法
csharp
public class Solution {
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];
}
else{
//swap
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
}
return -1;
}
}
复习：2022-05-02
csharp
public class Solution {
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 temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
return -1;
}
}