哈希表、in-place方法、快慢指针
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。
这个题目和之前有个题很像,数组除了两个数字,其余数字都是出现了两次
这两道题都能用万能解法,哈希表
这道题除了哈希表还有一种方法:in-place,也叫下标定位法
数组里每个数组都会指向下一个下标,当numbers[i] == numbers[numbers[i]]时,numbers[i]为重复的数字,在此之前,需要一直交换numbers[i]和numbers[numbers[i]],直到i != numbers[i],就是自己指向自己
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
for (int i=0; i<length; ++i) {
// 不相等就一直交换
while (i != numbers[i]) {
if (numbers[i] != numbers[numbers[i]]) {
swap(numbers[i], numbers[numbers[i]]);
}
else {
*duplication = numbers[i];
return true;
}
}
}
return false;
}
};
顺便把哈希表的解法也带上
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
map<int, int> res_map;
for(int i=0;i<length;i++)
{
if(res_map[numbers[i]]!=0)
{
*duplication = numbers[i];
return true;
}
res_map[numbers[i]]++;
}
return false;
}
};
这道题我有想到一个方法,就是快慢指针,龟兔赛跑算法,但是我理解了这个算法的目的,快慢指针可以检测出数组是否存在环,但是,不能确定sings hi都存在重复的数字,因为形成环不一定需要重复数字,例如[2,1,3,0,5],这里的2、1、0构成环,所以快慢指针会返回2,这里也罢错误的记录下
int fast=numbers[0];
int slow=numbers[0];
while(true)
{
fast=numbers[numbers[fast]];
slow=numbers[slow];
if(fast==slow)
{
break;
}
}
fast=numbers[0]; //充值快指针
while(true)
{
fast=numbers[fast];
slow=numbers[slow];
if(fast=slow)
{
*duplication=fast;
return true;
}
}
}