数组中的重复元素题解
数组中重复的数字
http://www.nowcoder.com/questionTerminal/6fe361ede7e54db1b84adc81d09d8524
解法一，O(N)时间复杂度，O(N)空间复杂度的方法，使用哈希来存储出现过的元素次数，如果出现次数大于2，则返回
代码如下:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int duplicate(vector<int>& numbers) {
int len=numbers.size();
if(len==0)
{
return -1;
}
unordered_map<int,int> num_cnt_map;
for(int i=0;i<len;i++){
//判断是不是合法
if(numbers[i]>len)
{
return -1;
}
num_cnt_map[numbers[i]]++;
if(num_cnt_map[numbers[i]]>1)
{
return numbers[i];
}
std::cout<<num_cnt_map[numbers[i]]<<endl;
}
return -1;
}
};
解法二，O(N)时间复杂度，和O(1)的空间复杂度
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
void swap(int &a,int &b){
int temp=a;
a=b;
b=temp;
}
int duplicate(vector<int>& numbers) {
int len=numbers.size();
if(len==0){
return -1;
}
for(int i=0; i<len;i++){
//判断不不合法的输入
if(numbers[i]>len)
{
return -1;
}
while(numbers[i]!=i)
{
if(numbers[i]==numbers[numbers[i]])
{
return numbers[i];
}
else
{
swap(numbers[i],numbers[numbers[i]]);
}
}
}
return -1;
}
};
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int count_num(vector<int> numbers,int start,int end)
{
int count=0;
for(auto num:numbers)
{
if(num>=start&&num<=end)
{
count++;
}
}
return count;
}
int duplicate(vector<int>& numbers) {
int len=numbers.size();
if(len==0){
return -1;
}
int start=0;
int end=len-1;
while(end>=start)
{
int mid=(end+start)/2;
int count=count_num(numbers, start, mid);
if(start==end)
{
if(count>1)
{
return start;
}
else
{
break;
}
}
if(count>(mid-start+1))
{
end=mid;
}
else{
start=mid+1;
}
}
return -1;
}
};
这种类似二分方法只能过90%，因为当n是偶数，划分2边区间大小一样，2边分配个数相同，或者是每边分配的个数恰好和坐标个数相等，则无法判断