这种方法的时间复杂度和辅助空间是多少？
这种方法的时间复杂度和辅助空间是多少？
提问于 2019-01-07 00:06:31
这种方法的时间复杂度和辅助空间是多少？谁能告诉我并解释一下结果？
public Set<T> findRepeatedValues(List<T> list){
Set<T> set = new HashSet<>();
Set<T> repeatedValues = new HashSet<>();
for (T i: list) {
if (!set.add(i)) {
repeatedValues.add(i);
}
}
return repeatedValues;
}如果我像下面这样测试我的代码会发生什么？
@Test
public void findRepeatedStrings(){
List<String> stringList = new ArrayList<String>(Arrays.asList("ali","mahdi","hadi","mahdi","mojtaba","mohammad","mojtaba"));
RepeatedValues repeatedValues = new RepeatedValues();
Set values = repeatedValues.findRepeatedValues(stringList);
for (Object i :
values) {
System.out.println(i);
}
}回答 2
Stack Overflow用户
发布于 2019-01-07 00:52:34
时间复杂度
代码的时间复杂度应该是O(n)，其中n是list中元素的数量。原因：
for (T i : list) { // iterates through all the 'n' elements
if (!set.add(i)) {
repeatedValues.add(i);
}
}空间复杂性
另一方面，由于您使用Set临时存储值，因此在最坏的情况下，您的Set所需的空间为：
Set<T> set = new HashSet<>(list.size()); // all elements are unique因此，您的解决方案的空间复杂性也将是O(n)。当然，n是一个与列表大小相同的值。如果列表的大小增加，所需的空间也会增加。
输出
public void printRepeatedStrings(){
List<String> stringList = Arrays.asList("ali","mahdi","hadi","mahdi","mojtaba","mohammad","mojtaba");
RepeatedValues<String> repeatedValues = new RepeatedValues<>(); // type 'T' bound
repeatedValues.findRepeatedValues(stringList)
.forEach(System.out::println); // prints ["mahdi","mojtaba"]
}Stack Overflow用户
发布于 2019-01-07 01:21:42
复杂性
时间复杂度is O(n)
- Space O(n)
is
解释
public Set<T> findRepeatedValues(List<T> list){
// both sets contains n elements: hence space complexity is O(n)
Set<T> set = new HashSet<>();
Set<T> repeatedValues = new HashSet<>();
// iterate over list only once: hence time complexity is O(n)
for (T i: list) {
// HashSet add has O(1) time complexity
if (!set.add(i)) {
repeatedValues.add(i);
}
}
return repeatedValues;
}测试
您的测试不正确。您必须检查返回的Set是否包含所需的数据。它可能看起来像：
public static void findRepeatedStrings() {
List<String> list = Arrays.asList("ali", "mahdi", "hadi", "mahdi", "mojtaba", "mohammad", "mojtaba");
Set<String> values = new RepeatedValues<String>().findRepeatedValues(list);
MatcherAssert.assertThat(values, IsCollectionWithSize.hasSize(2));
MatcherAssert.assertThat(values, IsIterableContainingInOrder.contains("mahdi", "mojtaba"));
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54063363
复制相关文章
相似问题