創建字典：防止多次添加同一個字的方法

我需要創建一個方法來確定我想要添加到我的String []字典中的單詞是否已添加。我們不允許在這個項目中使用ArrayList，只有數組。創建字典：防止多次添加同一個字的方法

我開始了這個

public static boolean dictHasWord(String str){ 
    for(int i = 0; i < dictionary.length; i++){ 
     if(str.equals(dictionary[i])){ 
      return true; 
     } 
    } 
    return false; 
}

然而，我的教授告訴我，不要用這個，因爲它是一個線性函數O（n），而不是有效的。我還有什麼可以解決這個問題的方法？

來源

2015-10-24 Frank

您是否允許使用Arrays類？ http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html –

您瞭解了哪些數據結構可以被允許使用？有幾個明顯的答案，但如果它們涉及到你已經學習的數據結構，那麼這是一個測試，以確保你已經學會了它，並且我不願意給你答案;如果你還沒有了解它們，期望你自己去找出它們太多了。如果不知道真正的限制和上下文的其餘部分，很難回答這樣的問題。 – ajb

我們只允許使用字符串數組創建我們的字典。沒有ArrayList或類似的東西。唯一的其他限制是我們無法調用Arrays.sort（）或Arrays.binarySearch（）。 – Frank

這是如何快速搜索具有良好可讀性的數組的示例。我會建議使用這種方法來搜索你的數組。

import java.util.*; 

public class test { 

public static void main(String[] args) { 
    String[] list = {"name", "ryan" 
    }; 
    //returns boolean here 
    System.out.println(Arrays.asList(list).contains("ryan")); 
    } 
}

來源

2015-10-24 03:05:59 Ryan

這仍然是一個O（n）解決方案。 – ajb

定義O（n）解決方案？這是線性搜索的另一個術語嗎？ – Ryan

我會研究一個遞歸的方式來排序，如果你不尋找線性的 – Ryan

如果你被允許使用Arrays類作爲您的任務的一部分，你可以整理你的數組，並使用二進制搜索，而不是，這不是爲O（n）。

public static boolean dictHasWord(String str){ 
    if(Arrays.binarySearch(dictionary, str) != -1){ 
    return true; 
    } 

    return false; 
}

請記住，您必須先排序。

編輯：
關於編寫自己的實現，這裏是一個sample讓你走。以下是javadocs for compareTo()。下面的示例代碼爲another sample（基於int的示例），顯示了遞歸和非遞歸之間的區別，特別是在Java中。

來源

2015-10-24 03:13:53

是的，我們可以使用數組類，但是我們不能調用Arrays.sort或使用它的搜索方法 – Frank

我們必須創建自己的排序方法，然後在添加每個單詞後立即調用我們的排序方法。 – Frank

根據上面的評論，這聽起來像你有你需要的一切，除了實際的搜索方法，但你無法使用已經提供的。爲什麼不實施你自己的？ http://www.vogella.com/tutorials/JavaAlgorithmsSearch/article.html#binarysearch_implementation –

儘管在這種情況下它可能是一種矯枉過正，但是散列表不會是O（n）。

這使用的事實是，每個字符串都可以通過hashCode()轉換爲int，而相等的字符串將產生相同的散列。

我們的字典可以被聲明爲：

LinkedList<String>[] dictionary;

在每個地方几個字符串可以駐留換句話說，這是由於可能發生的碰撞（不同串產生相同結果）。

加法，最簡單的解決辦法是：

public void add(String str) 
{ 
    dictionary[str.hashCode()].add(str); 
}

但爲了做到這一點，你需要做一個數組的大小等於1小於最大hashCode()功能。這對你來說可能太多了。所以我們可以做一點區別：

public void add(String str) 
{ 
    dictionary[str.hashCode()%dictionary.length].add(str); 
}

這樣我們總是修改哈希。爲了獲得最好的結果，你應該讓你的字典大小一些素數，或者至少是單個素數的一個次方。

然後，當你想測試你做，你在原來的有什麼字符串的存在，但是你用你從哈希得到具體LinkedList：

public static boolean dictHasWord(String str) 
{ 
    for(String existing : dictionary[str.hashCode()%dictionary.length]) 
    { 
     if(str.equals(existing)){ 
      return true; 
     } 
    } 
    return false; 
}

此時你可能問：「不是O（n）？」。答案是不是，因爲哈希函數沒有考慮數組中元素的數量。你會給你的數組留下更多的內存，你將會遇到更少的碰撞，並且更多的這種方法將會轉向O（1）。

如果有人發現這個答案尋找真正的解決方案（不是家庭作業）。然後只需使用HashMap。

來源

2015-10-24 04:34:41 v010dya

創建字典：防止多次添加同一個字的方法

回答

相關問題