我正在尝试使用字符串对仅包含小写字母的列表进行排序:
alphabet = "abcdefghijklmnopqrstuvwxyz".
那就是不使用排序,并且只具有O(n)的复杂度。
我去那里:
def sort_char_list(lst):
alphabet = "abcdefghijklmnopqrstuvwxyz"
new_list = []
length = len(lst)
for i in range(length):
new_list.insert(alphabet.index(lst[i]),lst[i])
print (new_list)
return new_list
对于此输入:
m = list("emabrgtjh")
我得到这个:
['e']
['e', 'm']
['a', 'e', 'm']
['a', 'b', 'e', 'm']
['a', 'b', 'e', 'm', 'r']
['a', 'b', 'e', 'm', 'r', 'g']
['a', 'b', 'e', 'm', 'r', 'g', 't']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'j']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'h', 'j']
['a', 'b', 'e', 'm', 'r', 'g', 't', 'h', 'j']
似乎一路上出现了问题,而且我似乎无法理解为什么..如果有人能启发我,那太好了。
最佳答案
您正在寻找桶分类。这里:
def sort_char_list(lst):
alphabet = "abcdefghijklmnopqrstuvwxyz"
# Here, create the 26 buckets
new_list = [''] * len(alphabet)
for letter in lst:
# This is the bucket index
# You could use `ord(letter) - ord('a')` in this specific case, but it is not mandatory
index = alphabet.index(letter)
new_list[index] += letter
# Assemble the buckets
return ''.join(new_list)
至于复杂性,由于
alphabet
是预定义的固定大小的字符串,因此在其中搜索字母最多需要26个操作,这相当于O(1)
。因此,总体复杂度为O(n)