Какова временная сложность HashMap.containsValue() в java?

Question

я получил проблему решить в O(n) временной сложности:

«? Учитывая список чисел и числа х найти, если есть любые 2 номеров в списке, которые добавляют до й»

И это мое решение:

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) потому, что я должен объяснить сценарий, где мой вход может содержать одинаковые значения. Например, в приведенном выше случае я могу иметь набор входных значений {3,6,4,4,7} для соответствия sum 8, который должен возвращать true.

Модификация времени моего решения зависит от сложности метода HashMap.containsValue(). Прошу пролить некоторый свет на сложность времени метода containsValue() и предложить мне, если есть лучшее решение для вышеупомянутой проблемы с точки зрения сложности времени. Спасибо.

Answer 1

чтобы ответить на этот вопрос в названии - как упомянуто другими, containsValue о (п), потому что без ключа он не знает, где он находится, и алгоритм должен перейти все значения, сохраненные на карте.

Чтобы ответить на вопрос в теле вашего вопроса - о том, как его решить, просто подумайте, действительно ли действительно нужна общая карта, которая может подсчитать, сколько экземпляров вы видели для каждого номера. Я имею в виду, только время, которое вам позаботится, если есть более одного вида номера, когда это 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; 

Answer 2

HashMap - это хранилище ключей, которое может получить доступ к его ключам со сложностью O (1). Однако, проверяя значение, HashMap ничего не может сделать, но проверить все значения и посмотреть, соответствуют ли они тому, который вы ищете. Следовательно, сложность O (n), где n - количество элементов в HashMap.

В другом примечании: вы просматриваете примитивные значения (int) в коллекции своего бокс-типа (целое число). Это означает, что каждый раз, когда вы вызываете метод на HashMap, Java должен указывать вам примитивные значения: http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

Answer 3

HashMap.containsValue - это O (n). Но n - это не точно размер карты, а размер хэш-таблицы, потому что containsValue проходит через все элементы таблицы, если даже размер карты = 0. Предположим, мы создали пустую карту с начальной емкостью = 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; 
}