我写了下面的代码,这个代码应该在列表中找到以某个前缀开头的所有元素,面试官问O()代码有什么困难,我回答了O(n),其中n是列表中元素的个数,在我看来,这是错误的答案,因为招聘人员非常失望。正确答案是什么?为什么?你知道吗
def count_elemets(list_elements, prefix):
result = []
for i in list_elements:
if i.startswith(prefix):
result.append(i)
return result
正确答案是什么?为什么?你知道吗
Tags:
我看了一下
有几点需要考虑。首先for循环是O(n),匹配字符的个数(比如k)使得复杂度为O(k*n)(仍然可以认为是O(n))。你知道吗startswith
函数的实现。你知道吗另一点是,似乎
startswith
函数可以将tuple
作为前缀参数,如果元组中存在任何前缀(以该前缀开始),则返回True
。所以也有人认为前缀元组的大小也是相关的。你知道吗不过,这些都可以被认为是O(n),我不知道你的面试官是否要求你给出一个更具体的答案,但我认为他应该更好地解释一下在答案中你到底需要什么。你知道吗
如果您想看一下,下面是实现。你知道吗
https://github.com/python/cpython/blob/master/Objects/unicodeobject.c
相关问题 更多 >
编程相关推荐