在Java中HashMap.containsValue（）的时间复杂度是多少？ [英] What is the time complexity of HashMap.containsValue() in java?
问题描述
我在 O（n）时间复杂度时遇到了问题：
I was given a problem to solve in O(n) time complexity :
给出一个列表数字和数字x。查找列表中是否有任何2个加起来为x的数字？
"Given a list of numbers and number x. Find if there any 2 numbers in the list that add up to 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）因为，我必须考虑我的输入可能包含相同值的场景。例如，在上面的例子中，我可以为 true 。
I am using HashMap.containsValue() instead of using a HashSet.contains() which surely has a complexity of O(1) because, I have to account for the scenario where my input might contain identical values. For example, in the above case, I can have a set of input values {3,6,4,4,7} to be matched for the sum 8, which should return true.
我的上述解决方案的时间复杂度取决于关于 HashMap.containsValue（）方法的复杂性。请详细说明 containsValue（）方法的时间复杂度，并建议我在时间复杂度方面是否有更好的解决方案来解决上述问题。谢谢。
My above solution's time complexity depends on the complexity of HashMap.containsValue() method. Please shed some light on the time complexity of containsValue() method and suggest me if there is any better solution for the above problem in terms of time complexity. Thank you.
推荐答案
要回答标题中的问题 - 正如其他人所提到的， containsValue 是O（n），因为没有键它不知道它在哪里，算法必须遍历存储在地图中的所有值。
To answer the question in the title - as mentioned by others, containsValue is O(n), because without the key it doesn't know where it is and the algorithm has to go over all the values stored in the map.
要回答问题正文中的问题 - 如何解决问题 - 只需考虑一下是否需要一个可以计算每个数字看到多少个实例的通用地图。我的意思是，如果一个数字的外观不止一个是x / 2，那么你只关心 时间，对吗？那对我来说就像一个角落的味道。只需添加一个检查该角落情况的测试 - 例如在您的set-construction循环中嵌入 if（numberList [i] == requiredSum / 2）half ++ ，然后 if（requiredSum％2 == 0&& half == 2）之后返回true （参见下面的其他变体）。
To answer the question in the body of your question - on how to solve it - just consider whether you really need a general map which can count how many instances have you seen of each number. I mean, the only time you'd care if there's more than one appearance of a number is when it's x/2, right? That smells like a corner case to me. Just add a test that checks for that corner case - something like embedding if (numberList[i] == requiredSum/2) half++ during your set-construction loop, and then if (requiredSum % 2 == 0 && half == 2) return true after it (see other variation below).
然后你可以迭代整个集合，对每个项目检查 requiredSum-item 是否也出现在集合中。
Then you can just iterate over the set and for each item check whether requiredSum-item also appears in the set.
总结（尽可能提前退出）：
To summarize (with early exits when possible):
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;
这篇关于在Java中HashMap.containsValue（）的时间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
