@@ -0,0 +1,1793 @@
+/**%0A * Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least%0A * one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.%0A *%0A * Note: You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space.%0A * Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be%0A * repeated more than once.%0A *%0A * Tags: Array, Two Pointers, Binary Search%0A * Similar Problems: (H) First Missing Positive, (M) Single Number, (M) Linked List Cycle II, (M) Missing Number%0A */%0Apublic class FindDupNum %7B%0A%0A    /**%0A     * Floyd's loop detection%0A     * Two pointers, O(n)%0A     */%0A    public int findDuplicate1(int%5B%5D nums) %7B%0A        int slow = 0;%0A        int fast = 0;%0A        while (true) %7B%0A            slow = nums%5Bslow%5D;%0A            fast = nums%5Bnums%5Bfast%5D%5D;%0A            if (slow == fast) break;%0A        %7D%0A        int find = 0;%0A        while (slow != find) %7B%0A            slow = nums%5Bslow%5D;%0A            find = nums%5Bfind%5D;%0A        %7D%0A        return find;%0A    %7D%0A%0A    /**%0A     * Binary Search, O(nlogn)%0A     * count: how many numbers are below the half value%0A     * if count %3E mid, dup in lower range%0A     * else dup in upper range%0A     */%0A    public int findDuplicate2(int%5B%5D nums) %7B%0A        int n = nums.length - 1;%0A        int l = 0, r = n;%0A        while (l %3C r) %7B%0A            int m = l + (r - l) / 2;%0A            int count = countBelow(nums, m);%0A            if (count %3E m) r = m;%0A            else l = m + 1;%0A        %7D%0A        return l;%0A    %7D%0A%0A    public int countBelow(int%5B%5D nums, int target)%7B%0A        int res = 0;%0A        for (int num : nums)%0A            if (num %3C= target) res++;%0A        return res;%0A    %7D%0A%7D%0A%7D%0A

add 287 FindDupNum