[Python] 配列内で同じ整数を探す

正の整数の配列の中に、同じ整数があるかどうか探します。

ただし、整数の最大値は、配列のサイズより小さいものとします。

総当たり

総当たりで同じ整数があるか探します。

時間計算量は\( O(N^2) \) になります。

def find_duplicate_brute_force(array):

    found_duplicates = set()
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[i] == array[j]:
                found_duplicates.add(array[i])
    
    print('found_duplicates_BF', list(found_duplicates))

メモ配列

配列が見つかった際にメモを取る配列を使います。

時間計算量は\( O (N) \) になりますが、空間計算量も \( O (N) \) になります。

def find_duplicate_memo(array):
    found_duplicates = set()
    memo_array = [-1 for _ in range(len(array))]
    
    for num in array:
        if memo_array[num] == -1:
            memo_array[num] = -memo_array[num]
        else:
            found_duplicates.add(num)

    print('found_duplicates_MEMO', list(found_duplicates))

既存の配列をメモに使う

既存の配列を同じ数字が既にあるかのメモに使うことで、時間計算量\( O (N) \) 空間計算量\( O(1) \) を実現します。

具体的には、配列は正の整数のみで、最大値は配列のサイズより小さいという条件があるので、この配列自体をメモとして使うことができ、その整数をインデックスとする値に -1 をかけることで、既に存在することをメモします。

配列内の整数が負になってしまっても、絶対値をつけることで、常に正の整数に変換することができます。

def find_duplicate_abs(array):
    
    found_duplicates = set()
    for num in array:
        if array[abs(num)] > 0:
            array[abs(num)] = -array[abs(num)]
        else:
            found_duplicates.add(abs(num))

    print('found_duplicates_ABS', list(found_duplicates))

まとめます。

def find_duplicate_brute_force(array):

    found_duplicates = set()
    for i in range(len(array)):
        for j in range(i+1, len(array)):
            if array[i] == array[j]:
                found_duplicates.add(array[i])
    
    print('found_duplicates_BF', list(found_duplicates))

def find_duplicate_memo(array):
    found_duplicates = set()
    memo_array = [-1 for _ in range(len(array))]
    
    for num in array:
        if memo_array[num] == -1:
            memo_array[num] = -memo_array[num]
        else:
            found_duplicates.add(num)

    print('found_duplicates_MEMO', list(found_duplicates))
        
def find_duplicate_abs(array):
    
    found_duplicates = set()
    for num in array:
        if array[abs(num)] > 0:
            array[abs(num)] = -array[abs(num)]
        else:
            found_duplicates.add(abs(num))

    print('found_duplicates_ABS', list(found_duplicates))


if __name__ == '__main__':
    array = [ 1, 2, 5, 1, 3, 4, 5]
    
    # found_duplicates_BF [1, 5]
    find_duplicate_brute_force(array)
    
    # found_duplicates_MEMO [1, 5]
    find_duplicate_memo(array)

    # found_duplicates_ABS [1, 5]
    find_duplicate_abs(array)