LeetCode——重复数字

1
2

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。
假设只有一个重复的整数，找出这个重复的数。

示例 1
输入: [1,3,4,2,2]
输出: 2

说明：

 1. 不能更改原数组（假设数组是只读的）。
 2. 只能使用额外的 O(1) 的空间。
 3. 时间复杂度小于 O(n2) 。
 4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

思路

把每个数字放到自己对应的下标处，如果其他位置上有和自己相同的数，则存在重复的数进行输出。

代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
		int i,temp;		// 由于申请了额外的temp，内存消耗会占用一定的空间
        for(int i=0;i<nums.size();++i){
            while(nums[i]!=i){
                if(nums[nums[i]]==nums[i]){
                    return nums[i];
                }
                temp=nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=temp;
            }
        }
        return 0;
    }
};

过程

nums=[1，3，4，2，2]

$i$	判断	交换	更新
$i=0$	$nums[0]=1 \neq 0$； $nums[1]=3 \neq 1$	$nums[1]=1$； $nums[0]=3$	$[3，1，4，2，2]$
$i=1$	$nums[1]=1$；继续循环	$-$	$-$
$i=2$	$nums[2]=4 \neq 2$； $nums[4]=2 \neq 4$	$nums[2]=2$； $nums[4]=4$	$[3，1，2，2，4]$
$i=3$	$nums[3]=2 \neq 3$ $nums[3]=2=nums[2]$	$-$	输出重复数字：$2$