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.

---

要求

• 不能修改数组（数组只读）
• 空间复杂度\(\Theta(1)\)
• 时间复杂度小于\(\Theta(n^2)\)

---

思路

这道题的突破口是数的范围，即对于n+1个数中的每个数x都有：1 <= x <= n ,所以可以通过下标来遍历数组(将每个数当做下标来遍历数组*):

因为一定存在唯一一个重复的数（可以重复很多次），所以一定会形成环，所以只要找到环入口，它的前驱一定是那个重复的数，期间可以做剪枝。做法参考寻找单链表环的入口。

---

Code

int findtheDupNum(const vector<int> &v){
    int p1, p2;
    int pre;
    p1 = p2 = 0;
    pre = 0;
    do{
        p1 = v[p1];
        p2 = v[v[p2]];
    }while(v[p1] != v[p2]);
    //剪枝
    if (p1 != p2)
    {
        return v[p1];
    }
    p2 = 0;
    while (v[p1] != v[p2]){
        pre= p2;
        p2 = v[p2];
        p1 = v[p1];
        //cout << v[p1] << " " << v[p2] << endl;
    }
    if (p1 == p2){
        return v[pre];
    }
    else{
        return v[p1];
    }
}