題目：給定一個(gè)字符類型數(shù)組chas，判斷chas中是否所有的字符都只出現(xiàn)過一次

要求1: 時(shí)間復(fù)雜度為O(N)的算法

思路：使用哈希表，記錄每個(gè)字符出現(xiàn)是否在哈希表里出現(xiàn)，如果沒有出現(xiàn)，則添加; 若重復(fù)出現(xiàn)則返回False

def isUnique(L):if L == None or len(L) = 1:return Truedict_ = {}for item in L:if item in dict_:return Falseelse:dict_[item] = 1return True

要求2，空間復(fù)雜度為O(1)的算法

1、先將數(shù)組排序，再判斷當(dāng)前字符是否等于前一個(gè)字符即可

2、滿足復(fù)雜度要求的算法只有非遞歸的堆排序

def HeapSort(L):if L == None or len(L) == 1:return for i in range(len(L)):heapInsert(L,i)size = len(L)-1swap(L,0,size)while size > 0:heapify(L,0,size)size -= 1swap(L,0,size)def heapify(L,index,size):left = 2 * index + 1while left < size:if left+1 < size and L[left+1] > L[left]:largest = left + 1else:largest = leftif L[largest] > L[index]:largest = largestelse:largest = indexif largest == index:breakswap(L,largest,index)index = largestleft = 2 * left +1def 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] = tmpdef isUnique2(chas):if chas == None or len(chas) == 1:return TrueHeapSort(chas)for i in range(1,len(chas)):if chas[i-1] == chas[i]:return Falsereturn True

若堆排序不是很了解，請(qǐng)參考我的另一篇文章：https://mp.csdn.net/postedit/94294293

?

總結(jié)

以上是生活随笔為你收集整理的判断字符串数组中是否所有字符只出现了一次的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。