Find the Duplicated Number

题目

Find the Duplicated Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

解题报告

理解题意

• 给定一个大小为 n+1 的数组，其中每一个数字都是在 1--N 的区间内, 证明至少有一个重复数字是存在的，假定只有唯一的一个重复数字，找到他
• 不能修改数组, 排序也就不能用了。
• 常量空间
• 运行时间要比 N^2要小，那就只剩下 O(n) O(nlogn) O(logn) 的算法可用。

理解例子

• 2 -> 4 -> 3 = 342
• 5 -> 6 -> 4 = 465
• 342 + 465 = 807
• 答案 : 7 -> 0 -> 8

思路

• 证明至少存在一个重复数字，如果元素是[1,n] 那么就存在 n 个不同的数字，分别将每一个位置都占据了，当数字个数为 n+1 时，那么最少有一个数字是重复的
• 由于数组的 n+1 个元素的取值范围为 1..n，假定映射关系为 f，那么就存在一个函数 f(i) --> 可以取到 nums[i]，重复的情况就是说存在另一个数字 j，在i != j的前提下，存在 f(i) == f(j)， 那么剩下的问题就是如何将 f 表示出来
• 就是说使用函数 f。遍历整个数组，总会存在一个位置导致没有办法结束，走入无限循环，也就是类似链表存在环。
• 证明过程：证明过程

代码

class Solution {
public:
    int findDubplicated(vector<int>& nums) {
        int slow = 0, fast = 0;
        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }
        int find = 0;
        while (true) {
            slow = nums[slow];
            find = nums[find];
            if (slow == find)
                break;
        }
        return find;
     }
};