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.

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

中文描述：
給出一個數(shù)組 nums 包含 n + 1 個整數(shù)，每個整數(shù)是從 1 到 n (包括邊界)，保證至少存在一個重復(fù)的整數(shù)。假設(shè)只有一個重復(fù)的整數(shù)，找出這個重復(fù)的數(shù)。

Example
Given nums = [5,5,4,3,2,1] return 5
Given nums = [5,4,4,3,2,1] return 4

題目分析：
這道題知道和二分法有關(guān)， 但是一開始并不知道如何去確定判斷答案是否猜對的判斷條件，看了答案以后發(fā)現(xiàn)和lintCode183 wood cut的判斷條件是類似的。 這個數(shù)組是從1到n的， 一共n + 1個元素。 假設(shè)這個數(shù)組是 [7, 6, 5, 4, 4, 3, 2, 1] 那么假設(shè)隨機(jī)選一個數(shù) 3， 小于等于3 的元素個數(shù)只有3個， 那就是1， 2， 3。 如果選2， 小于等于2的就只有兩個元素。 那如果選5， 小于等于5的元素是6， 選6和選7也是一樣， 小于或等于他們自身的元素個數(shù)都要多1個。 因此以這個條件就可以作為判斷二分猜答案是否正確的標(biāo)準(zhǔn)了。

代碼如下：

public class Solution {
        /**
         * @param nums: an array containing n + 1 integers which is between 1 and n
         * @return: the duplicate one
         */
        public int findDuplicate(int[] nums) {
            // write your code here
            int l = 1, r = nums.length - 1;

            while(l + 1 < r)
            {
                int mid = l + (r - l) / 2;
                if(count(nums, mid) <= mid)
                    l = mid;
                else
                    r = mid;

            }

            if(count(nums, l) <= l)
                return r;
            return l;

        }

        public int count(int[] nums, int mid)
        {
            int count = 0;
            for(int num: nums)
            {
                if(num <= mid)
                    count++;
            }
            return count;
        }
    }

結(jié)合之前的分析， 如果count函數(shù)返回的結(jié)果小于或者等于mid， 說明重復(fù)的那個數(shù)不在這個范圍內(nèi)， 那么移動左指針， 反之， 移動右指針。 最后同樣要再判斷一下到底是l 還是r。