题解 | #数组中重复的数字#

数组中重复的数字：最直观的想法就是，使用一个unordered_set来存储访问过的数据，然后从头到尾遍历numbers数组，如果在unordered_set中找到当前数据，则表明该数据在数组中重复出现，并直接返回当前数据，反之，则表明该数据暂时未在数组中出现，并将该数据加入到unordered_set中，遍历完整个数组如果还未找到，则返回-1。

int duplicate(vector<int>& numbers) 
{
	unordered_set<int> data;
    for(int i=0;i<numbers.size();i++)
    {
    	if(data.find(numbers[i])!=data.end())
        return numbers[i];
        else data.emplace(numbers[i]);
    }
    return -1;
}

idea：返回数组中所有重复的数字？使用一个vector<int>类型的变量result来存储数组中所有重复的数字，在上述基础上，如果在unordered_set中找到当前数据，不是直接返回当前数据，而是将当前数据加入到result中，遍历完整个数组后，根据result是否为空来相应的返回-1或者result。

优化：由于长度为n的数组里的所有数字都在0~n-1范围内，所以可以考虑使用原地哈希，即在原有数组的基础上，将对应的数字存放在对应的下标上，比如下标0存放元素0、下标1存放元素1……。首先从头到尾遍历数组，然后判断当前下标i是否与将当前下标i中所存放的元素numbers[i]相等，如果相等，则表示对应的下标中已经存放着对应的数字，反之如果不相等，则判断当前下标i中存放的元素numbers[i]是否与将当前下标i中所存放的元素numbers[i]作为下标后所对应的数组元素numbers[numbers[i]]相等，如果是，则表示该元素numbers[i]重复并返回，反之将两者互换。

int duplicate(vector<int>& numbers) 
{
	for(int i=0;i<numbers.size();i++)
    {
  	//i表示当前下标 numbers[i]表示当前下标所存放的元素 numbers[numbers[i]]表示将当前元素作为数组下标后所对应的元素
    	//while(i!=numbers[numbers[i]]) //这样也是可以的
    	while(i!=numbers[i]) //判断下标是否与下标对应存储元素相等
        {
        	if(numbers[i]==numbers[numbers[i]])
            return numbers[i];
            swap(numbers[i],numbers[numbers[i]]);
        }
     }
        return -1;
 }

//示例 1 0 1

//表明 i==numbers[numbers[i]] 元素不一定归正 但是i=2时会进行两次交换