287. Find the Duplicate Number -M !!!

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

 

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

A:

解法1：二分法

此题的二分法思想非常巧妙，将所有元素和n/2进行比较，如果大于n/2的个数多于n/2个，说明重复的元素必定在n/2到n之间。以此类推，可以不断缩小折半考察范围。  

举个general的例子，如果考察范围是left~right，则考察 mid = left+(right-left)/2。如果比mid大的元素个数，多于mid~n之间的个数，则说明重复的元素在mid~n之间。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        // binary search of the range of from 1 to n
        int n = nums.size() -1; 
        int bottom = 1, top = n; // inclusive
        while(bottom < top){
            int mid = (bottom + top)/2;
            // count that # is bigger than range
            int count = 0;
            for(const auto &val : nums){
                if(val >= bottom && val <= mid){
                    ++count;
                }
            }
            if(count > mid-bottom +1){
                top = mid;
            }else{
                bottom = mid+1;
            }
        }
        return bottom;
    }
};

解法2： 按照digit 数数，1如果超过一半，就是1,否则就是0

              这个方法思路就不对

解法2：快慢指针

此题还有一个非常绝妙的算法。将1~N个数放在N+1个位置上，那么val->index将会出现一个一对多的映射，反之，index->val将会有一个多对一的映射。而其余的则是一一映射。于是这些index和val势必会有一部分构成一个环。

举个例子：2,4,1,3,1 从index到val的映射关系是：1->2, 2->4, {3,5}->1, 4->3，其中1->2->4->3->1就构成了一个环。可见，这个环的入口就是重复的数字。

于是此题可以联想到 142. Linked List Cycle II，用快慢指针来确定一个linked list中环的入口。算法是，先用快慢指针做追及（快指针的速度比慢指针快一倍），直到他们相遇的位置；再用一个慢指针从起点开始，和在追及位置的慢指针共同前进。他们再次相遇的地方就是环的入口。

Mistakes: