《剑指Offer》 不修改数组找出重复的数字 Python实现

1 问题描述

《剑指Offer》page41. 在一个长度为 n+1 的数组里，所有数字都在 1～n 范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组 {2,3,5,4,3,2,6,7}, 那么对应的输出是重复的2 或者3.

2 我的代码

class Solution(object):
    def findDuplicate(self,numbers):
        def countRange(head, tail):
            count = 0
            for ele in numbers:
                if ele >= head and ele <= tail:
                    count += 1
            return count

        if not numbers:
            return -1
        n = len(numbers)
        start = 1
        end = n-1
        while end >= start:
            middle = (end - start)//2 + start
            ct = countRange(start, middle)
            if end == start:
                if ct > 1:
                    return start
                else:
                    break

            if ct > (middle - start +1):
                end = middle
            else:
                start = middle +1
        return -1

3 注意

需要指出的是，这种算法不能保证找出所有重复的数字。例如该算法不能找出示例数组中重复的数字2。这是因为在1～2 的范围内有1 和 2 两个数字，这个范围的数字也出现两次，此时我们不能确定是每个数字各出现一次还是某个数字出现了两次。