287. 寻找重复数

https://leetcode-cn.com/problems/find-the-duplicate-number/

牛逼的快慢指针与二分查找灵活运用。

class Solution {
    public int findDuplicate(int[] nums) {
        // ***快慢指针***
        int slow = 0, fast = 0;
        // 0. 寻找环内相遇点
        // 将数值与下标看成是链表，因为有重复值存在的原因。一定可以成环
        do {
            // 所以，num[value] = 假设出的 key
            slow = nums[slow];
            // 嵌套就表示 快指针走两步
            fast = nums[nums[fast]];
        } while (slow != fast);
        // 1. slow 和 fast 相等，也就是相遇点
        // 2. 寻找环的入口点
        // 这里涉及数学理论，可能以后的快慢指针客户已考虑这种思想
        // 就是需要找到他们成环的起始点
        // 记住，第二次就是 before 为开头，after 为相遇点
        int before = 0, after = fast;
        while (before != after) {
            before = nums[before];
            after = nums[after];
        }
        // 循环结束，环的入口点就是重复元素
        return before;
    }
}

快慢指针辅助理解：
比如数组：[3，6，1，4，6，6，2]

整体思路如下： 第一阶段，寻找环中的节点 a) 初始时，都指向链表第一个节点nums[0]； b) 慢指针每次走一步，快指针走两步； c) 如果有环，那么快指针一定会再次追上慢指针；相遇时，相遇节点必在环中 第二阶段，寻找环的入口节点（重复的地址值） d) 重新定义两个指针，让before，after分别指向链表开始节点，相遇节点 e) before与after相遇时，相遇点就是环的入口节点 第二次相遇时，应该有： 慢指针总路程 = 环外0到入口 + 环内入口到相遇点 (可能还有 + 环内m圈) 快指针总路程 = 环外0到入口 + 环内入口到相遇点 + 环内n圈 并且，快指针总路程是慢指针的2倍。所以：环内n-m圈 = 环外0到入口 + 环内入口到相遇点。 把环内项移到同一边，就有：环内相遇点到入口 + 环内n-m-1圈 = 环外0到入口 这就很清楚了：从环外0开始，和从相遇点开始，走同样多的步数之后，一定可以在入口处相遇。所以第二阶段的相遇点，就是环的入口，也就是重复的元素。

class Solution {
    public int findDuplicate(int[] nums) {
        // 查找的是 1-N 自然序列中谁是 target
        // 定义左右指针
        int left = 1;
        int right = nums.length - 1;
        while (left <= right) {
            // 计算中间值
            int mid = (left + right) / 2;
            // 对当前 mid 计算 count 值
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            // 判断 count 和 mid 本身的大小关系
            // count 小于 mid ，按之前的理论，target 值肯定大于 mid，反之小于
            if (count <= mid) {
                left = mid + 1;
            } else {
                right = mid;
            }
            // 左右指针重合时，找到 target
            if (left == right) {
                return left;
            }
        }
        return -1;
    }
}

二分查找辅助理解：

• 以target为界，对于比target小的数i，数组中所有小于等于它的数，最多出现一次（有可能被多出现的target占用了），所以总个数不会超过i。
• 对于比target大的数j，如果每个元素都只出现一次，那么所有小于等于它的元素是j个；而现在target会重复出现，所以总数一定会大于j。

用数学化的语言描述就是： 我们把对于1~N内的某个数i，在数组中小于等于它的所有元素的个数，记为count[i]。则：当i属于[1, target-1]范围内，count[i] <= i；当i属于[target, N]范围内，count[i] > i。

所以要找target，其实就是要找1~N中这个分界的数。所以我们可以对1~N的N个自然数进行二分查找，它们可以看作一个排好序的数组，但不占用额外的空间。

在O(N logN)时间复杂度内，这个很简单，但是还是高

class Solution {
    public int findDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
                 int left = 1, right= nums.length - 1;
        while (left<=right){
            int count = 0;
            int mid =left+ (right-left)/2;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i]<=mid){
                    count++;
                }
            }
            if (count<=mid){
                left = mid+1;
            }else{
                right = mid;
            }
            // 左右指针一直在移动，一定可以重合，那就是答案
            if (left==right){
                return left;
            }
        }
        return -1;
    }
}

class Solution {
    public int findDuplicate(int[] nums) {
              int fast = 0;
        int low = 0;
        do {
            fast = nums[nums[fast]];
            low = nums[low];
        } while (low != fast);
        int out = 0;
        int inner = low;
        while (out!=inner){
            out = nums[out];
            inner = nums[inner];
        }
        return out;
    }
}