字符串以給定前綴

-1

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; 
}

函數應該返回與給定前綴開頭的所有單詞。
列表中的代碼是一個有序的ArrayList。此代碼具有O(n)複雜性。
我該如何改進？
例如運行在log(n)時間。

來源

2012-12-26 Walt Watson

如果您交換數據結構，請查看前綴搜索嘗試。 –

因爲你可以讓所有的字符串（或其中的大多數）以相同的前綴開始，所以它不可能比列表中的字符串數量中的O（n）更好地運行。如果必須多次執行多次搜索，則只能獲得性能提升。 –

以前有過答案，注意，由於列表已排序，所以可以找到匹配範圍的開始和結尾，其中O（ log n）二進制搜索和調用List.subList（）來提取O（1）時間的範圍，而不管找到多少個單詞。由於某種原因它似乎已被刪除 - 我不知道爲什麼，因爲它對我來說似乎是正確的。 –

是的，你可以

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; 
}

來源

2012-12-26 13:43:09

這與我的一樣。 –

問題是 - 你能做到這一點在O(logn)時間？
如果list中的一半元素具有所需的前綴，該怎麼辦？您需要將該列表的一半添加到新列表中 - 這仍然是O(n)。

來源

2012-12-26 13:47:45

字符串以給定前綴

回答

相關問題