搜索从某个前缀开始的列表元素的函数有什么困难?

2024-03-29 10:34:34 发布

您现在位置:Python中文网/ 问答频道 /正文

我写了下面的代码,这个代码应该在列表中找到以某个前缀开头的所有元素,面试官问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: 答案代码元素列表prefix人员defcount
1条回答
网友
1楼 · 发布于 2024-03-29 10:34:34

我看了一下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

相关问题 更多 >