面试题3(1):找出数组中重复的数字
在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
解题思路
- 先对数组进行排序，再查找重复元素
int duplicate(int *a,int length,int *dup)
{
if(*a == NULL || length <0)
{
return false;
}
for(int i =0;i<length;i++)
{
if(a[i]<0 || a[i]>length-1)
{
return false;
}
}
for(int i = 0;i<length-1;i++)
{
for(int j = i+1;j<length;j++)
{
if(a[i]>a[j])
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
for(int i = 0;i<length-1;i++)
{
if(a[i] == a[i+1])
{
*dup = a[i];
return true;
}
}
return false;
}
- 根据下标来查找，因为题目给出长度为n的数组数字在0~n-1的范围内，故可以判断a[i]==a[a[i]]来判断，若不等，则交换。
int duplicate(int *a,int length,int *dup)
{
if(*a == NULL || length <0)
{
return false;
}
for(int i =0;i<length;i++)
{
if(a[i]<0 || a[i]>length-1)
{
return false;
}
}
for(int i = 0;i<length;++i)
{
while(a[i] != i)
{
if(a[i] == a[a[i]])
{
*dup = a[i];
return true;
}
int temp = a[i];
a[i] = a[temp];
a[temp] = temp;
}
}
return false;
}
- 利用STL中的map
- 用到map的find()函数
map.find(key); 查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end(); - map的插入
通过数组的方式插入值
mapStu[3] = “小刘";
mapStu[5] = “小王"；
bool deplicate_1(int *a,int length,int *dup)
{
map<int,int> map_dup;
if(*a == NULL || length <0)
{
return false;
}
for(int i =0;i<length;i++)
{
if(a[i]<0 || a[i]>length-1)
{
return false;
}
}
for(int i = 0;i<length;i++)
{
if(map_dup.find(a[i]) != map_dup.end())
{
*dup = a[i];
return true;
}
else
{//若没有出现过，则加1
map_dup[a[i]] = 1;
}
}
return false;
}
