剑指offer面试题3：数组中重复的数字（Python实现）

"""
面试题3：数组中重复的数字
在一个长度为n的数组里所有数字都在0~n-1的范围内，某些数字是重复的，找出任意一个重复的数字
"""


def duplicate1(numbers: list, length: int) -> int:
    """
    修改原数组
    """
    if numbers == [] or length <= 0:
        return -1

    for i in range(length):
        while numbers[i] != i:
            if numbers[numbers[i]] == numbers[i]:
                return numbers[i]
            else:
                temp = numbers[i]
                numbers[i] = numbers[temp]
                numbers[temp] = temp
    return -1


def duplicate2(numbers: list, length: int) -> int:
    """
    不修改原数组
    """
    if (numbers == [] or length <= 0):
        return -1

    left = 0
    right = length - 1
    while(right >= left):
        mid = left + (right - left) // 2
        count = countRange(numbers, length, left, mid)
        if(right == left):
            if(count > 1):
                return left
            else:
                break
        if(count > (mid - left + 1)):
            right = mid
        else:
            left = mid + 1
    return -1


def countRange(numbers: list, length: int, left: int, right: int) -> int:
    if(numbers == []):
        return 0

    count = 0
    for i in range(length):
        if(numbers[i] >= left and numbers[i] <= right):
            count += 1
    return count


if __name__ == '__main__':
    numbers_list = [2, 3, 1, 0, 2, 5, 3]
    print('改变数组：')
    print(duplicate1(numbers_list, len(numbers_list)))
    print('##############')
    print('不改变数组：')
    print(duplicate2(numbers_list, len(numbers_list)))