java - 我的代码的运行时间是 O(n) 还是 O(n * m)?
问题描述
public List<List<Integer>> groupThePeople(int[] groupSizes) {
List<List<Integer>> groups = new ArrayList<List<Integer>>();
for(int i = 0; i < groupSizes.length; i++) {
boolean added = false;
int index = 0;
while(index < groups.size() && !added) {
List<Integer> temp = groups.get(index);
int size = groupSizes[temp.get(0)];
if(size == groupSizes[i] && temp.size() < groupSizes[i]) {
temp.add(i);
added = true;
}
else {
index++;
}
}
if(!added) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(i);
groups.add(temp);
}
}
return groups;
}
我认为这段代码在 O(n) 处运行,因为我只遍历数组一次,但由于内部循环,它也可以是 O(n * m) 吗?
解决方案
似乎在最好的情况下,复杂性可能是O(N)
- 当输入数组groupSizes
包含 N 个不小于 N 的相同元素时{5, 5, 5, 5, 5}, {10, 10,... 10} (10 elements), etc.
。
如果所有 N 个元素都不同,则复杂度为O(N^2)
(实际上,~N^2/2
) - 这是最坏的情况,当groupSize
包含 N 个零或一(N > 1)时也是可能的。
更新
可以重构此代码以提供 O(N) 复杂性,借助映射将输入数组中的数字存储为键,并将输入数组中的索引作为值收集到列表(2D 列表)中。
使用比较好,LinkedHashMap
因为它提供了O(1)的插入和获取操作,并且维护了插入的顺序。
public static List<List<Integer>> groupThePeople(int... groupSizes) {
// System.out.println("plain: " + Arrays.toString(groupSizes));
Map<Integer, List<List<Integer>>> map = new LinkedHashMap<>();
for (int i = 0; i < groupSizes.length; i++) {
// create a 2D list as a default value for the given map
List<List<Integer>> value = map.computeIfAbsent(groupSizes[i], k -> new ArrayList<>(Arrays.asList(new ArrayList<Integer>())));
// new list needed if no size left in the last available inner list
if (!value.get(value.size() - 1).isEmpty() && groupSizes[i] <= value.get(value.size() - 1).size()) {
value.add(new ArrayList<>());
}
// add index to the inner list
value.get(value.size() - 1).add(i);
}
return map.values() // convert Collection<List<List<Integer>>>
.stream()
.flatMap(x -> x.stream())
.collect(Collectors.toList());
}
测试
groupThePeople(0, 1, -1, -1, 3, 3, 3, 1, 2, 3, 0).forEach(System.out::println);
groupThePeople(10, 10, 10, 10, 10, 10, 10, 10, 10, 10).forEach(System.out::println); // all numbers the same
groupThePeople(10, 15, 15, 15, 10, 10, 10, 10, 10, 10).forEach(System.out::println); // without splitting nested lists
输出:
plain: [0, 1, -1, -1, 3, 3, 3, 1, 2, 3, 0]
[0]
[10]
[1]
[7]
[2]
[3]
[4, 5, 6]
[9]
[8]
plain: [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
plain: [10, 15, 15, 15, 10, 10, 10, 10, 10, 10]
[0, 4, 5, 6, 7, 8, 9]
[1, 2, 3]
类似的方法可以使用 Stream API 来实现,虽然它看起来更冗长。
此外,此实现是两遍,需要第二遍将索引的内部列表拆分为大小小于键数的子列表。
public static List<List<Integer>> groupThePeopleStream(int... groupSizes) {
// System.out.println("stream: " + Arrays.toString(groupSizes));
return IntStream
.range(0, groupSizes.length)
.mapToObj(i -> Map.entry(groupSizes[i], i)) // entry: number -> index
.collect(Collectors.groupingBy(Map.Entry::getKey, LinkedHashMap::new, // convert to map: number -> list of indexes
Collectors.mapping(Map.Entry::getValue, Collectors.toList())))
.entrySet()
.stream()
//.peek(e -> System.out.println(e.getKey() + ":"))
.flatMap(e -> e.getKey() >= e.getValue().size() // need to split list of indexes?
? Stream.of(e.getValue()) // no, store a single index
: IntStream.iterate(0, x -> x < e.getValue().size(), x -> x + Math.max(1, e.getKey())) // yes, preparing indexes: 0, N, 2N..
.mapToObj(x -> e.getValue().subList(x, Math.min(x + Math.max(1, e.getKey()), e.getValue().size())))
)
//.peek(x -> System.out.println("\t" + x))
.collect(Collectors.toList());
}
相同测试数据的输出(包括调试打印):
stream: [0, 1, -1, -1, 3, 3, 3, 1, 2, 3, 0]
0:
[0]
[10]
1:
[1]
[7]
-1:
[2]
[3]
3:
[4, 5, 6]
[9]
2:
[8]
stream: [10, 10, 10, 10, 10, 10, 10, 10, 10, 10]
10:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
stream: [10, 15, 15, 15, 10, 10, 10, 10, 10, 10]
10:
[0, 4, 5, 6, 7, 8, 9]
15:
[1, 2, 3]
推荐阅读
- php - 正则表达式匹配前导和尾随空格
- docker - 容器中的 CPU 指令
- javascript - Javascript 模板文字 - 函数调用
- blazor-server-side - Blazor 未选择由 javascript 更改的文本字段值
- tinymce - TinyMCE 5:带有(不可编辑)引用的自定义块引用
- html - 使此按钮在其边框内可点击的问题
- symfony - 教义:如何使用查询构建器进行嵌套查询?
- c++ - 从高度图中读取高度值
- javascript - 使用 Google 表格中的图像填充 Jquery 自动完成功能
- javascript - 通过特定键的值在多个数组中查找对象