数组中重复的元素-剑指offer

r囧r小猫 2022-07-28 09:14 129阅读 0赞

## 题目描述：在一个长度为n的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入的长度为7的数组\{2,3,1,0,2,5,3\};那么对应的输出是重复的数字2或者3。 ##

看到这个题目首先想到的就是，先排序，排完序再找重复的数字，很easy。代码如下：

bool find_duplicate(int numbers[], int length, int &duplicate)
    {
    	if (numbers == NULL || length <= 0 || duplicate == NULL)
    	{
    		return false;
    	}
    	sort(numbers, numbers + length);//STL快速排序
    	for (int i = 0; i < length - 1; i++)
    	{
    		if (numbers[i] == numbers[i + 1])
    		{
    			duplicate = numbers[i];
    			return true;
    		}
    	}
    	return false;
    }

时间复杂度O(NlogN)，空间复杂度O(1)。但时间复杂度过高。  
看书上说可以用hash表来做这个，我忽然想到了set。set的底层可以用RB-tree，也可以用hash。原理类似。代码如下：

bool find_duplicate(int numbers[], int length, int &duplicate)
    {
    	if (numbers == NULL || length <= 0 || duplicate == NULL)
    	{
    		return false;
    	}
    	set<int> s;
    	set<int>::iterator it;
    	s.insert(numbers[0]);
    	for (int i = 1; i < length; i++)
    	{
    		if ((it = s.find(numbers[i])) != s.end())
    		{
    			duplicate = numbers[i];
    			return true;
    		}
    		else
    		{
    			s.insert(numbers[i]);
    		}
    	}
    	return false;
    }

由于set的插入，查找，删除时间复杂度均为O(logN)，所以平均时间复杂度为O(N)。空间复杂度为O(N)。这是增加了额外的内存空间，也不好。  
下面来看看书上说的时间复杂度为O(N),空间复杂度为O(1)的算法。  
首先从头到尾扫描这个数组的每个元素。当扫描到下标为i的元素时，首先比较这个元素（记为m）是不是等于索引i。如果是，接着扫描下一个元素。如果不是，再拿它和索引为m的元素比较。如果它和索引为m的元素相等。就找到了一个重复的数字了。此时停止扫描即可。如果它和索引为m的元素不相等，那么就把它和索引为m的元素交换，把m放到索引为m的地方去。接下来重复比较，交换。直到发现一个重复的数字。  
 为什么这样就行呢？首先根据题目要求，长度为n数组，所以元素都在0-n-1范围。比如有数组array\_test\[5\]=\{1,0,3,2,4\}，这种情况没有元素重复，经过上述操作，array\_test\[5\]=\{0,1,2,3,4\}.所以索引对应的元素就是索引本身的值。但是一旦有重复的元素，比如array\_test\[5\]=\{0,1,2,2,3\}（该种情况已经排好）。不同的索引会对应同一个值，比如索引2对应的值为2，索引3对应的数值也为2。那么扫描到索引3，里面的元素为2。再到索引为2的地方查找，发现对应的元素也为2.就找到了重复的一个数字。这种方法的目的就是把一个打乱的数组调整为索引==内容。理论上是一个萝卜一个坑，但可惜不是，哈哈~。所以~~~~~~代码如下：

bool find_duplicate(int numbers[], int length, int &duplicate)
    {
    	if (numbers == NULL || length <= 0 || duplicate == NULL)
    	{
    		return false;
    	}
    	for (int i = 0; i < length; i++)
    	{
    		if (numbers[i] != i)
    		{
    			if (numbers[numbers[i]]!=numbers[i])
    			{
    				int temp = numbers[i];
    				numbers[i] = numbers[numbers[i]];
    				numbers[temp] = temp;
    			}
    			else
    			{
    				duplicate = numbers[i];
    				return true;
    			}
    		}
    	}
    	return false;
    }