java中HashMap.containsValue（）的時間複雜度是多少？

我被賦予了O(n)時間複雜度來解決問題：java中HashMap.containsValue（）的時間複雜度是多少？

「？鑑於數字和數字X的列表中找到，如果有任何2個號碼加起來x的名單」

這是我的解決方案：

public class SumMatchResult { 

    public static void main(String[] args){ 
    int[] numberList = {6,1,8,7,4,6}; 
    int requiredSum = 8; 
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum); 
    if(isSumPresent) { 
     System.out.println("Numbers exist"); 
    }else { 
     System.out.println("Numbers donot exist"); 
    } 
    } 

    private static boolean checkSumPresentHash(int[] numberList, int requiredSum) { 
    Map<Integer, Integer> m = new HashMap<Integer,Integer>(); 
    int count = 0; 
    for(int i=0;i<numberList.length;i++){ 
     m.put(i, numberList[i]); 
    } 
    for(int i=0;i<numberList.length;i++){ 
     if(m.containsValue(requiredSum - numberList[i])){ 
     count++; 
     } 
    } 
    if(count>1){ 
     return true; 
    } 
    return false; 
    } 

}

我使用HashMap.containsValue()而不是使用HashSet.contains()這肯定有一個的O(1)複雜性，因爲，我必須考慮到在我的輸入可能包含相同的值的情況。例如，在上述情況下，我可以爲sum 8匹配一組輸入值{3,6,4,4,7}，該值應返回true。

我上面的解決方案的時間複雜度取決於HashMap.containsValue()方法的複雜性。請澄清containsValue()方法的時間複雜性，並建議我是否有更好的解決上述問題的時間複雜性。謝謝。

來源

2013-05-26 Vishnu Vedula

也許你應該使用'Set'，而不是'Map'。 – johnchen902

我會好奇看到一個算法，在O（n）時間解決這個問題。我不確定這是可能的。 –

如何保持一個單獨的'HashMap'作爲他的鍵的值的第一個？通過這種方式，你可以立即知道蝙蝠（'O（1）'）是否存在價值。這是'O（2n）'的空間，但是，嘿，它就是這樣。 – acdcjunior

要回答標題中的問題 - 如其他人所說，containsValue爲O（n），因爲沒有鑰匙，它不知道它在哪裏，算法一直走在所有存儲在地圖中的值。

要回答你的問題 - 如何解決它的問題 - 只需考慮你真的需要一個普通的地圖，可以統計你看到每個數字有多少實例。我的意思是，只有你關心的時間，如果一個數字的外觀不止一個是x/2的時候，對吧？這對我來說就像是一個角落案件。只需添加一個測試來檢查該角落案例 - 就像在設置構建循環中嵌入if (numberList[i] == requiredSum/2) half++，然後在if (requiredSum % 2 == 0 && half == 2) return true之後（請參閱下面的其他變體）。

然後您可以遍歷該集合，併爲每個項目檢查是否requiredSum-item也出現在集合中。

總結（早期退出時可能）：

Set<Integer> seen = new HashSet<Integer>(); 
boolean halfSeen = false; 
for (int num : numberList) { 
    if (num == requiredSum/2 && requiredSum % 2 == 0) { 
     if (halfSeen) return true; 
     halfSeen = true; 
    } else { 
     seen.add(num); 
    } 
} 
for (int num : seen) { 
    if (seen.contains(requiredSum - num)) return true; 
} 
return false;

來源

2013-05-26 08:47:06 Oak

+1關於角落案例的非常好的一點（'if（numberList [i] == requiredSum/2）'）。大整體解決方案！ – acdcjunior

@Oak：非常感謝您的解決方案。不過，稍微修正一下，seen.add（num）應該在else部分，否則，即使只有一個num == requiredSum/2，它將被添加到該集合中，下一個循環返回true，這是錯誤的。 –

@VishnuVedula好點，固定。這個改變還需要將兩分檢查移動到封閉的if中，因爲如果'requiredSum'是7，那麼我們確實希望保持3'看到'。 – Oak

HashMap本質上是一個鍵值存儲，它可以訪問它的複雜度爲O（1）的鍵。然而，檢查一個值，HashMap沒有什麼能做，但是檢查所有的值，看看它們是否與你正在搜索的值相同。因此，複雜度爲O（n），其中n是HashMap中元素的數量。

在另一個註釋中：您正在查找它的盒裝類型（整數）的集合中的原始值（int）。這意味着每次您在HashMap上調用方法時，Java都需要將原始值框起來：http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

來源

2013-05-26 08:12:42 rethab

未來肯定會記住拳擊和拆箱。謝謝:) –

HashMap.containsValue複雜度爲O（n）。但是n不完全是地圖大小，而是散列表大小，因爲如果偶數地圖大小= 0，containsValue會遍歷所有表格元素。假設我們創建了一個初始容量= 1024的空映射。containsValue必須通過1024個元素散列表數組：

public boolean containsValue(Object value) { 
    if (value == null) 
     return containsNullValue(); 

    Entry[] tab = table; 
    for (int i = 0; i < tab.length ; i++) 
     for (Entry e = tab[i] ; e != null ; e = e.next) 
      if (value.equals(e.value)) 
       return true; 
    return false; 
}

來源

2013-05-26 08:32:25

java中HashMap.containsValue（）的時間複雜度是多少？

回答

相關問題