03. 数组中重复的数字

一、题目描述

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

限制：

2 <= n <= 100000

二、解题思路

1、使用原地置换的法

数组元素的 索引和值是 一对多的关系。 因此，可遍历数组并通过交换操作，使元素的索引与 值一一对应（即 nums[i]=i ）。这样就能通过索引映射对应的值，起到与字典等价的作用。

nums[i] 2 3 1 0 2 5 3
i 0 1 2 3 4 5 6

算法流程：

遍历数组 nums ，设索引初始值为 i=0 :

若nums[i]=i ： 说明此数字已在对应索引位置，无需交换，因此跳过；

若nums[nums[i]]=nums[i] ： 代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i] ；

否则： 交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。

若遍历完毕尚未找到，则返回 −1 。

①、判断vector容器是否为空；

②、初始值为 i=0开始遍历数组 nums :

③、判断nums[i]与i的关系，如果nums[i]=i ，则说明此数字已在对应索引位置，无需交换；如果不相等，则进行交换 temp = nums[nums[i]]; nums[nums[i]]=nums[i]; nums[i]=temp; 直到nums[i]=i; i+1进入下一次遍历；

④、如果nums[nums[i]]=nums[i] ，代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i]，即为我们要找的重复数字

复杂度分析：

时间复杂度 O(N)： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1)；
空间复杂度 O(1) ： 使用常数复杂度的额外空间。

具体程序实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <vector>
using namespace std;

void printVecotr(vector<int>& v)
{
	for(vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
//使用原地置换法
class Solution {
public:
    int findRepeatNumber(vector<int> nums) 
    {
         //首先判断数组是否为空
        if(nums.size() == 0)
        {
            return -1;
        }
    	for(int i = 0;i< nums.size();i++)
        {
        	while(nums[i]!=i)
        	{
            	if(nums[i]==nums[nums[i]])
            	{
            		return nums[i];
            	}    
            	int temp = nums[nums[i]];
            	nums[nums[i]]=nums[i];
            	nums[i]=temp;       
        	}
    	}
    	return -1; 
    }
};

int main()
{
	vector<int> v1;
	int a[] = {2,3,1,0,2,5,3};
	auto length = sizeof(a)/sizeof(a[0]);
	for(int i = 0; i < length; i++)
	{
		v1.push_back(a[i]);
	}
	printVecotr(v1);
	cout  << length << endl;
	Solution S;
	auto num = S.findRepeatNumber(v1);
	cout  << num << endl;
	
	return 0;
}

输出：

1
2
3
0 1 1 0 2 5 3 
7
1

程序具体的实现流程：

①、i = 0, nums[0] = 2 != 0;进入交换：temp = nums[nums[0]] = 1, nums[nums[0] = nums[0] = 2,nums[0] = 1;

则数组顺序变为：{1,3,2,0,2,5,3}

②、i = 0, nums[0] = 1 != 0; 进入交换：temp = nums[nums[0]] = 3, nums[nums[0] = nums[0] = 1,nums[0] = 3;

则数组顺序变为：{3,1,2,0,2,5,3}

③、i = 0, nums[0] = 3 != 0; 进入交换：temp = nums[nums[0]] = 0, nums[nums[0] = nums[0] = 3,nums[0] = 0;

则数组顺序变为：{0,1,2,3,2,5,3}

④、此时有nums[0] = 0；nums[1] = 1；nums[2] = 2；nums[3] = 3；

⑤、i = 4, nums[4] = 2 != 4; 进入if判断：nums[4] = nums[nums[4]]) = 2，则返回2

参考链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/solution/mian-shi-ti-03-shu-zu-zhong-zhong-fu-de-shu-zi-yua/