1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] == i + 1) continue;
            int t = nums[i];
            nums[i] = 0;
            while (nums[t - 1] != 0) {
                cout << nums[t - 1] << endl;
                if (nums[t - 1] == t) {
                    return t;
                }
                int p = t - 1;
                t = nums[t - 1];
                nums[p] = p + 1; 
            }
            nums[t - 1] = t;
        }
        return 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[0];

        // 找到相遇点
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        // 找到入口点
        slow = nums[0];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};