我正在尝试使用字符串对仅包含小写字母的列表进行排序:

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)

10-06 09:16
查看更多