Find the Duplicate Number

这道题的第一个要求是不能修改数组，这样直接加n最后模n统计每个数出现次数的方法就不能用了，第二条是不能用额外空间，这样拿个桶来统计次数的方法也被排除了，第三条时间复杂度低于O(n^2)，这样暴力搜索的方法也不能用了，第四条则是保证有解且有可能有些元素是缺失的，这种情况下O(nlgn)的算法自然首先想到，而O(nlgn)最惯常的算法就是排序和二分答案了，这里排序不提，二分答案很明显是根据1-n的范围二分，每次拿中间值遍历整个数组去统计大于等于中间值的出现次数，最后拿这个次数和n与此中间值的距离进行比较，如果这个次数大于距离则说明重复值肯定在这半边的数范围里面，这样二分就形成了，另外此题的二分边界条件用模板写比较鲁棒

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        start, end = 1, length - 1

        while start + 1 < end:
            mid = start + (end - start) / 2
            if self.check(mid, nums, length - 1):
                start = mid
            else:
                end = mid

        if self.check(end, nums, length - 1):
            return end
        return start


    def check(self, num, nums, n):
        count = 0
        for value in nums:
            if value >= num:
                count += 1

        if count > n - num + 1:
            return True
        return False

稍微精简一些的二分写法

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        start, end = 1, n - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if self.check(mid, nums) > n - mid:
                start = mid
            else:
                end = mid

        if self.check(end, nums) > n - end:
            return end
        return start

    def check(self, target, nums):
        return sum([1 for num in nums if num >= target])

另外就是这类一个范围里面重复数多次出现经常用的O(n)算法了，就是和链表探环一个样，快慢指针跳，相交之后把另一个从新设成起点，最后同步往前移，相遇的点就是重复数出现的点

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow, fast = nums[0], nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]

        slow = 0
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]

        return slow