287. Find the Duplicate Number

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

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.

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

Thoughts

容易想到暴力法嵌套遍历时间复杂度O(n^2). 可以用hashset先把出现过的数字记下来，但这样空间复杂度为O(n)，不符合题目要求。 可以先排序，然后再遍历配合二分。但排序算法必须是heapsort才满足O(1)空间复杂度和O(nlgn)时间复杂度。 那有没有不用排序就能二分的解法呢？没想出来。。

后来看到别人分享的后恍然大悟。做不出来最主要原因是 审题不清 。题目里有一句很重要的each integer is between 1 and n (inclusive)没在意。

但即使注意到了，想用二分法做对还是不容易。因为它用到的关系为：不重复时数组中小于等于mid的数字数目应等于mid。 因此本题的二分不同寻常之处在于它的mid是index时，择半规则直接用的mid却不是用nums[mid]。 相应的，返回的也直接是start/end而不是nums[start/end]. 除此之外，它的二分法放在了外循环。

Code

class Solution {
    public int findDuplicate(int[] nums) {
        int start = 1, end = nums.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= mid) {
                     count++;
                }
            }

            if (count <= mid) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

Analysis

时间复杂度为O(nlgn), 空间复杂度O(1).

Ver.2

如果没有重复的并把数组每个元素看成是指针，从0开始蹦会类似在linked list上遍历，最后蹦出数组。当有重复元素时形成环，找环起始用检测环的Floyd算法：快慢指针。还可以阵对元素值对相应位置取负作为标记，当取负时发现已经是负数的也就是答案。

/*
* @lc app=leetcode id=287 lang=cpp
*
* [287] Find the Duplicate Number
*/

// @lc code=start
class Solution {
public:
   int findDuplicate(vector<int>& nums) {
       int slow = 0, fast = 0;
       while (true) {
           slow = nums[slow]; 
           fast = nums[nums[fast]];
           if (slow == fast) break;
       } 
       int head = 0;
       while (slow != head) {
           slow = nums[slow];
           head = nums[head];
       }
       return head;
   }
};
// @lc code=end