最有效的方法來搜索字符串數組的子字符串和返回多個值？

說你給包含數組：最有效的方法來搜索字符串數組的子字符串和返回多個值？

喬丹

JORD

安娜

羅布

RobJord

你想返回所有值的數組包含Jord（即Jord，Jordan，RobJord），什麼是最多高效的方式來做到這一點。

我正在使用Java，但是我是不允許使用java.util數組函數。

來源

2014-03-01 JWyatt

這種做法在我腦海中：

public ArrayList<String> search(String searchString, String[] names) 
{ 
    ArrayList<String> searchList = new ArrayList<String>(); 

    for (String name : names) 
    { 
    if(name.contains(searchString)) 
    { 
     searchList.add(name); 
    } 
    } 

    return searchList; 
}

現在搜索，使用此：

String[] names = {"Jordan", "Jord", "Anna", "Rob", "RobJord"}; 
String searchString = "Jord"; 

ArrayList<String> filterList = search(searchString, names);

它不使用java.util.Arrays方法，並且也得到一個乾淨的完成任務方式，更不用說，它的速度很快。

現在，如果你甚至不能用ArrayList，那麼你有兩種選擇：
1.自己實現ArrayList並使用它。
2.按照下面的方法：

public String[] search(String searchString, String[] names) 
{ 
    int size = getSize(searchString, names); 
    String[] searchList = new String[size]; 

    int index = 0; 
    for (String name : names) 
    { 
    if(name.contains(searchString)) 
    { 
     searchList[index++] = name; 
    } 
    } 

    return searchList; 
} 

// Returns appropriate size for the Search List 
private int getSize(String searchString, String[] names) 
{ 
    int size = 0; 
    for (String name : names) 
    { 
    if(name.contains(searchString)) 
    { 
     size++; 
    } 
    } 

    return size; 
}

來源

2014-03-01 20:01:25

謝謝，但不幸的是，我們不能使用ArrayList。基本上任何java.util都是禁止的。 – JWyatt

@Lecaille：更新了我的回答。 –

好，因爲這聽起來像功課，這對你來解決，但我會考慮這個非常英文的僞代碼。它避免使用java.util.*（例如ArrayList或Arrays類）並且僅使用基本結構。

count = 0 
for each item in the input 
    if the rule matches 
     increase count by 1 

create output array of size count 

target index = 0 
for each item in the input 
    if the rule matches 
     add the item to the output array at the target index, 
     and increase the target index by 1 

return the output array

此代碼是在complexityO(n)，即使它遍歷輸入（n）兩次，因爲這是一個常數因子，並O(2*n)是2*O(n)是O(n)。

現在，恆定界限可以是略微減少，而不是僅依靠第一通，也壓實在第一道次的值，然後只複製壓實值，這將是小於或等於n，到一個新的更小的陣列。它仍然是O(n)，但它可能有一個稍低的掛鐘時間..或它可能執行更糟糕取決於微妙的緩存/ JIT /數據因素。哦，現代電腦的有趣複雜！

有沒有簡單的方法來提高O(n)「效率」的界限 - 特別是不是一次運行。

來源

2014-03-01 20:02:15 user2864740

這將需要一些代碼得到一切成立，這將是可怕風格，但你可以在你的字符串轉換成字符數組，並有一個INT陣列，它代表的字母的ASCII值在「Jord」中，這樣你就可以通過基元而不是對象引用進行檢查。通過你檢查對字符到，隨着

'J', 'o', 'r', 'd' //74, 111, 114, 100

的國際價值評估它同樣條件塊，因爲你有這麼多強調效率，我只認爲這種瘋狂。我馬上就會說，將所有內容轉移到字符所需的時間有一個效率缺陷。在大型處理任務中，如在一個完整的1000頁電子書中檢查Jord是最好的選擇，因爲初始化只發生一次（或者我認爲可能有大量數據的大塊數據，但仍然有益）

//assuming its case sensitive: ascii values for 'J' 'o' 'r' 'd' 
int[] charArr = new int[]{74, 111, 114, 100};

同樣，它需要一些阻礙性能的設置，加上它的奇怪，但它確實給了您通過基本int驗證的好處。

另一個想法是考慮某些字母后面跟着另一個字母的統計數字。例如，「J」跟隨任何元音的可能性非常高，因此「J」後面跟着「o」，但仍然不是「Jord」因此是非常高的，因爲我們只有5個元音（加上y，那個怪異的人......）例如，你可能會得到「Jork」，並且你浪費了檢查「o」和「r」。因此，據說，也許最好將掃描儀向上移動幾個字母（或者您當前的數組索引計數器 - 無論採用哪種方式進行迭代），以在爲「J」建立匹配之後檢查「d」」。我認爲這會提高效率。

基本上我說的是，如果你按照迭代的方式逐字逐句檢查，第一步是匹配「J」，然後第二步將跳到跳過「 o「，然後檢查」r「或」d「。換句話說，找到一個候選人，並積極消除候選人

編輯︰我實際上說在第2步中檢查「d」，不考慮檢查「r」，直到第3步如果第2步檢查出，因爲這樣你的代碼將變得更簡單 - 從開始就開始，移動到最後，然後向後迭代到start + 1。如果你在步驟2中檢查「r」，那麼步驟3和4將是Zigzagging指數遍歷

來源

2014-03-01 20:46:28

最有效的方法來搜索字符串數組的子字符串和返回多個值？

回答

相關問題