文字配列にすべての文字が一度しか現れていないかどうかを判断する

文書ディレクトリ

は、文字配列中のすべての文字が1回だけ現れるかどうかを判断する

である.

文字が一意かどうかを判断する

時間複雑度O(N)アルゴリズム構想

対応コード

空間複雑度O(1)アルゴリズム構想

対応コード

文字配列にすべての文字が一度しか現れていないかどうかを判断する
文字が一意かどうかを判断する
【タイトル】1つの文字タイプ配列chas[]を与え、chasにすべての文字が1回しか現れていないかどうかを判断します.
【例】chas=[‘a’,‘b’,‘c’]、Trueを返す.chas=[‘1’,‘2’,‘1’]でFalseを返します.
【要求】以下の2つの異なる要求によってそれぞれ実現する

時間複雑度O(N)を実現する方法.

余分なスペースの複雑さをO(1)に保証する前提の下で、時間の複雑さをできるだけ低くする方法を実現してください.

時間複雑度O(N)アルゴリズムの考え方
辞書/集合/リスト統計では,再統計は繰返しであり,そうでなければ文字の一意時間複雑度はO(N)O(N)O(N),空間複雑度はO(N)O(N)O(N)O(N)であることが分かった.
対応するコード

#       ，     O(N)，     O(N)
def is_unique_time_first(arr):
    d = {}
    for i in range(len(arr)):
        if arr[i] in d:
            return False
        else:
            d[arr[i]] = 1
    return True
#     
if __name__ == '__main__':
    chas = ['a', 'b', 'c']
    print(is_unique_time_first(chas))  # True

    chas = ['1', '2', '1']
    print(is_unique_time_first(chas))  # False

空間複雑度O(1)アルゴリズムの考え方
まず並べ替えて、隣の文字が同じかどうかを確認します.同じものがあれば繰り返しです.そうしないと、文字は唯一並べ替え、バブル並べ替え、挿入並べ替え、時間複雑度O(N^2)、空間複雑度O(1)、条件を満たすスタック並べ替え、時間複雑度O(Nlogn)、空間複雑度O(1)、条件を満たす高速並べ替え、時間複雑度O(Nlogn)、空間複雑度は最低O(logN)集計ソート、時間複雑度O(NlogN)であり、補助配列が必要であり、空間複雑度はO(N)バケツソート、基数ソート、カウントソートなどの非比較ソートであり、時間複雑度はO(N)であるが、データの状況に関係する余分な空間が必要であるため、条件を満たさない
従って、最適化は、時間的複雑度O(N l o g N)O(NlogN)O(NlogN)、空間的複雑度O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O(1)O
対応するコード

#       ，     O(1)，     O(NlogN)
def is_unique_space_first(arr):
    heap_sort(arr)
    for i in range(1, len(arr)):
        if arr[i] == arr[i - 1]:
            return False
    return True

#    
def heap_sort(arr):
    #      
    for i in range(len(arr)):
        heap_insert(arr, i)
    #        ，    
    for i in range(len(arr)):
        swap(arr, 0, len(arr) - 1 - i)
        heapify(arr, 0, len(arr) - 1 - i)

#        
def heap_insert(arr, index):
    parent = (index - 1) // 2
    while parent >= 0 and arr[index] > arr[parent]:
        swap(arr, index, parent)
        index = parent
        parent = (index - 1) // 2

#        
def heapify(arr, index, size):
    left = 2 * index + 1
    while left < size:
        if arr[left] > arr[index]:
            if left + 1 < size and arr[left + 1] > arr[left]:
                swap(arr, index, left + 1)
                index = left + 1
            else:
                swap(arr, index, left)
                index = left
        elif left + 1 < size and arr[left + 1] > arr[index]:
            swap(arr, index, left + 1)
            index = left + 1
        else:
            break
        left = 2 * index + 1

#     
def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp


#     
if __name__ == '__main__':
    #      
    arr = [5, 3, 7, 1, 4]
    heap_sort(arr)
    print(arr)
    print()

    arr = [1, 3, 4, 2, 5]
    heap_sort(arr)
    print(arr)
    print()

    arr = [8, 5, 2, 9, 4, 2, 9, 9, 6, 8, 9, 1, 6, 3, 4, 5, 9, 6, 8, 5, 7, 3, 5, 6, 6, 7, 9, 6, 4, 8, 9, 4, 7, 5, 9, 2,
           2, 6, 1, 8, 3, 2, 5, 4, 6, 6, 7, 2, 1, 5, 7, 1, 7, 3, 2, 6, 1, 9, 6, 2, 3, 4, 9, 1, 3, 1, 6, 8, 1, 3, 1, 2,
           2, 5, 6, 2, 1, 4, 3, 5, 6, 8, 1, 8, 9, 1, 8, 1, 8, 3, 4, 4, 3, 1, 9, 6, 9, 5, 8, 7]
    heap_sort(arr)
    print(arr)
    print()
    
    chas = ['a', 'b', 'c']
    print(is_unique_space_first(chas))  # True

    chas = ['1', '2', '1']
    print(is_unique_space_first(chas))  # False

何か質問やアドバイスがあれば、コメントエリアでコメントや指摘を歓迎します.
時間と労力を費やしてくれてありがとう!