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

タイトル:1つの文字タイプ配列chasを与えて、chasの中ですべての文字が1回しか現れたことがないかどうかを判断します
要求1:時間複雑度O(N)のアルゴリズム
考え方:ハッシュテーブルを使用して、各文字がハッシュテーブルに現れるかどうかを記録し、現れなければ追加します.繰り返されるとFalseに戻ります

def isUnique(L):

    if L == None or len(L) = 1:
        return True

    dict_ = {}

    for item in L:
        if item in dict_:
            return False
        else:
            dict_[item] = 1

    return True

要求2,空間複雑度O(1)のアルゴリズム
1、配列を並べ替えてから、現在の文字が前の文字に等しいかどうかを判断すればよい
2、複雑度の要求を満たすアルゴリズムは非再帰的なスタックソートのみ

def HeapSort(L):

    if L == None or len(L) == 1:
        return 
    
    for i in range(len(L)):
        heapInsert(L,i)

    size = len(L)-1
    swap(L,0,size)

    while size > 0:
        heapify(L,0,size)
        size -= 1
        swap(L,0,size)
           

def heapify(L,index,size):
    
    left = 2 * index + 1
    while left < size:
        if left+1 < size and L[left+1] > L[left]:
            largest = left + 1
        else:
            largest = left

        if L[largest] > L[index]:
            largest = largest
        else:
            largest = index

        if largest == index:
            break

        swap(L,largest,index)
        index = largest
        left = 2 * left +1

def heapInsert(L,index):
    while L[index] > L[int((index-1)/2)]:
        swap(L,index,int((index-1)/2))
        index = int((index-1)/2)

def swap(L,i,j):
    tmp = L[i]
    L[i] = L[j]
    L[j] = tmp

def isUnique2(chas):

    if chas == None or len(chas) == 1:
        return True

    HeapSort(chas)
    for i in range(1,len(chas)):
        if chas[i-1] == chas[i]:
            return False

    return True

スタックのソートがよく分からない場合は、別の記事を参照してください.https://mp.csdn.net/postedit/94294293