Java 8 : map. 合并时间复杂度

Question

我试图找到下面代码的复杂性，因为 for 循环它将是 O(n * complexity_of_map.merge)

public int solution(int K, int[] A) {    
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int i =0; i < A.length; i++){
        map.merge(K - A[i], 1, Integer::sum);
    }   
    return Arrays.stream(A).map(element -> map.getOrDefault(element,0)).sum();
} 

谁能帮我理解上面代码和 map.merge() 的时间复杂度 在 Java 8 中。

Answer 1

引自 JDK 8 的 Javadoc: https://docs.oracle.com/javase/8/docs/api/java/util/Map.html#merge-K-V-java.util.function.BiFunction-

The default implementation is equivalent to performing the following steps for this map, then returning the current value or null if absent:

V oldValue = map.get(key);
V newValue = (oldValue == null) ? value :
          remappingFunction.apply(oldValue, value);
if (newValue == null)
    map.remove(key);
else
    map.put(key, newValue);

对于HashMap，put、remove和get都是O(1) >。您使用的 remappingFunction 是 Integer::sum ，与 n 无关。所以您解决方案中的 for 循环很简单 O(n)。

对于stream操作，stream + map + sum应该大致相当于一个简单的for循环，O(n)。您传递给 map() 的 lambda 正在调用 map.getOrDefault，这对于 HashMap 也是 O(1) >。所以总体上也是 O(n)。

所以你的解决方案很简单O(n)。