我写了下面的代码,代码应该找到列表中以某个前缀开头的所有元素,面试官问代码有什么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
正确答案是什么?为什么?
最佳答案
我研究了 startswith
函数的实现。
有一些要点需要考虑。首先,for 循环的时间复杂度为 O(n),并且匹配字符的数量(假设为 k)使得复杂度为 O(k*n)(仍然可以认为是 O(n))。
另一点是,如果元组中存在任何前缀(以该元组开头),则似乎 startswith
函数可以将 tuple
作为前缀参数前缀),则返回 True
。因此,人们也可能认为前缀元组的大小也是相关的。
但是,这些都可以被认为是 O(n),我不知道你的面试官是否要求更具体的答案,但我认为他应该更好地解释你在答案中到底需要什么。
如果您想看一下,这里是实现。
static PyObject *
unicode_startswith(PyObject *self,
PyObject *args)
{
PyObject *subobj;
PyObject *substring;
Py_ssize_t start = 0;
Py_ssize_t end = PY_SSIZE_T_MAX;
int result;
if (!stringlib_parse_args_finds("startswith", args, &subobj, &start, &end))
return NULL;
if (PyTuple_Check(subobj)) {
Py_ssize_t i;
for (i = 0; i < PyTuple_GET_SIZE(subobj); i++) {
substring = PyTuple_GET_ITEM(subobj, i);
if (!PyUnicode_Check(substring)) {
PyErr_Format(PyExc_TypeError,
"tuple for startswith must only contain str, "
"not %.100s",
Py_TYPE(substring)->tp_name);
return NULL;
}
result = tailmatch(self, substring, start, end, -1);
if (result == -1)
return NULL;
if (result) {
Py_RETURN_TRUE;
}
}
/* nothing matched */
Py_RETURN_FALSE;
}
if (!PyUnicode_Check(subobj)) {
PyErr_Format(PyExc_TypeError,
"startswith first arg must be str or "
"a tuple of str, not %.100s", Py_TYPE(subobj)->tp_name);
return NULL;
}
result = tailmatch(self, subobj, start, end, -1);
if (result == -1)
return NULL;
return PyBool_FromLong(result);
}
https://github.com/python/cpython/blob/master/Objects/unicodeobject.c
关于python - 搜索从某个前缀开始的列表元素的函数的 O(n) 难度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55501046/