我需要对字符串列表进行排序,其中每个字符串的长度为k
,并且每个字符串只包含字符{'a', 'b', 'c', 'd', 'e'}
。
我确实有以下限制:
O(k)
。你知道吗O(k)
[w/o考虑长度的返回列表n
]。你知道吗O(n*k*(5^k))
。你知道吗函数接收lst, k
,这是要排序的列表和列表中每个字符串的长度。我有两个方法string_to_int(), int_to_string()
,它们将长度为k
的字符串转换为[0,5^k)
范围内的数字,反之亦然,这些方法是双射。这些方法的时间复杂度都是O(k)
。你知道吗
我最好的尝试是:
def sort_strings(lst, k):
int_lst = []
for item in lst:
int_lst.append(string_to_int(item))
sorted_lst = []
for i in range(5**k):
if i in int_lst:
sorted_lst.append(int_to_string(k, i))
return sorted_lst
但是这里我创建了int_lst
,它的空间复杂度是O(n)
,而不是O(k)
。
有什么办法吗?你知道吗
你的时间限制太长了。这样就有足够的时间按顺序检查每个可能的长度为k的字符串,并将这些字符串与输入列表中的每个字符串进行比较。你知道吗
你能用它做什么?你知道吗
尝试重用
int_list
作为输出编辑:如果输入列表包含重复项,请考虑
while i in int_list[replace:]:
而不是if ....
。你知道吗相关问题 更多 >
编程相关推荐