java - 以给定前缀开头的字符串

Question

我有以下代码：

public List<String> function(String pre) {
    List<String> temp = new ArrayList<>();
    for(String str : list) {
        if(str.startsWith(pre)
            temp.add(str);
        if(str.charAt(0) > pre.charAt(0))
            break;
    }
    return temp;
}

该函数应返回以给定前缀开头的所有单词。
代码中的list是一个排序的ArrayList。这段代码很O(n)复杂。
我该如何改进它？
例如及时运行log(n)。

Answer 1

问题是——你能及时做到O(logn)吗？
如果其中的一半元素list具有所需的前缀怎么办？您需要将列表的那一半添加到新列表中 - 这仍然是O(n).

Answer 2

是的你可以

List<String> function(List<String> list, String pre) {
    List<String> temp = new ArrayList<>();
    for(String str : list) {
        if(str.startsWith(pre))
            temp.add(str);
    }
    return temp;
}