（python）《剑指offer》面试题3： 数组中的重复数字

面试题3： 数组中的重复数字

在长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但是不知道有几个数字重复了。
请找出数组中的重复数字。如输入长度为7的数组【2,3,1,0,2,5,3】，输出【2,3】

#coding = utf-8
def find_repeat_array_version1(ls):
    '''使用双层循环'''
    ## 时间复杂度O(n^2)
    repeat_item = []
    for index, i in enumerate(ls):
        if i in repeat_item:
            continue 
        for j in ls[index+1:]:
            if i == j:
                repeat_item.append(i)
                continue
    return repeat_item
    
def find_repeat_array_version2(ls):
    '''引用字典，单层循环'''
        ## 时间复杂度O(n), 但代价是大小为O(n)的哈希表
    repeat_item = []
    item = {}
    for index, i in enumerate(ls):
        if i in repeat_item:
            continue
        if index == 0:
            item[i] = 1
        if i in item:
            repeat_item.append(i)
            continue
        else:
            item[i] = 1
    return repeat_item

def find_repeat_array_version3(ls):
    '''从头到扫描数组，当扫描到下标为i的数字时，首先比较这个数字ls[i]?=i, if True, 扫描下一个数字；否则，if ls[ls[i]]?=ls[i],若是则为重复数字，否则将ls[i]放到正确下标的位置'''
    ## 时间复杂度O(n), 空间复杂度为O(1)
    repeat_item = []
    for index, i in enumerate(ls):
        if ls[index] == index:   #坐标位置正确
            continue 
        else:  # not true 
            if ls[i] == i:  #是否和i对应的位置数一样
                repeat_item.append(i)  # 同时在索引index处和i处出现i，重复！
            else:
                ls[i], ls[index] = ls[index], ls[i]  #把i换到正确的索引位置
    return repeat_item

## 若不修改数组找出重复数字？
## 创建一个长度为n的辅助数组
def find_repeat_array_version4(ls):
    auxiliary = [False] * len(ls)
    repeat_item = []
    for index, i in enumerate(ls):
        if auxiliary[i] == False:
            auxiliary[i] = i 
        else:
            repeat_item.append(i)
    return repeat_item

if __name__ == '__main__':
    ls = [2, 3, 1, 0, 2, 5, 3]
    print('version1 ->>> ', find_repeat_array_version1(ls))
    print('version2 ->>> ', find_repeat_array_version2(ls))
    print('version3 ->>> ', find_repeat_array_version3(ls))
    print('version4 ->>> ', find_repeat_array_version4(ls))

结果打印