lintcode 633. 寻找重复的数

链接

题里不让我们使用额外空间，同时不能使用暴力解法。

解法一：二分法

一直数字的范围是1~n， 取其中的中点mid，统计数组中的数字小于mid的个数，如果个数小于等于Mid， 则说明重复的数在mid后面，否则重复的数在mid前面。时间复杂度O(NlgN)

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 start = 1;
        int end = nums.length - 1;
        while(start + 1 < end){
            int mid = (end - start)/2 + start;
            if(count(nums, mid) <= mid){
                start = mid;
            }else{
                end = mid;
            }
        }
        if(count(nums, start) <= start){
            return end;
        }else{
            return start;
        }
       
    }
    int count(int[] nums, int k){
        int cnt = 0;
        for(int n: nums){
            if(n <= k){
                cnt++;
            }
        }
        return cnt;
    }
}

解法二：快慢指针法

可以把数组想成一个index和value的映射链表，可知value有重复的，所以一定会出现环的情况，快慢指针验证环并找交点。时间复杂度O(N)

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }
        return fast;
    }
}