2018-06-18 lintCode633 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.

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.

中文描述：
给出一个数组 nums 包含 n + 1 个整数，每个整数是从 1 到 n (包括边界)，保证至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

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

题目分析：
这道题知道和二分法有关， 但是一开始并不知道如何去确定判断答案是否猜对的判断条件，看了答案以后发现和lintCode183 wood cut的判断条件是类似的。 这个数组是从1到n的， 一共n + 1个元素。 假设这个数组是 [7, 6, 5, 4, 4, 3, 2, 1] 那么假设随机选一个数 3， 小于等于3 的元素个数只有3个， 那就是1， 2， 3。 如果选2， 小于等于2的就只有两个元素。 那如果选5， 小于等于5的元素是6， 选6和选7也是一样， 小于或等于他们自身的元素个数都要多1个。 因此以这个条件就可以作为判断二分猜答案是否正确的标准了。

代码如下：

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;
        }
    }

结合之前的分析， 如果count函数返回的结果小于或者等于mid， 说明重复的那个数不在这个范围内， 那么移动左指针， 反之， 移动右指针。 最后同样要再判断一下到底是l 还是r。