我正在为以下问题寻找更好的解决方案(时间和复杂性方面):
给定整数列表。首先打印所有第一个元素,然后打印所有第二个元素,依此类推。
示例:{{1,2,3}, {5,4,6}}
打印 1,5,2,4,3,6
解决方案 1:我可以使用两个 for 循环迭代列表列表,但时间复杂度将增加到 O(n^2)
。有没有更好的方法使用 O(n)
实现上述结果?
最佳答案
简短回答:否。
长答案:假设你想在一个循环中完成它。如果所有内部列表的长度相同,并且如果您可以快速随机访问列表元素(例如数组列表),则可以计算下一个元素的位置。伪 Java 代码:
int totalElements = outerListSize * innerListSize;
for(int targetPos = 0; targetPos < totalElements; targetPos++) {
//For the outer list, choose the next index until reaching
//the end, then roll over
int outerIndex = targetPos % outerListSize;
//For the inner lists, choose 0 until the outer lists roll
//over, then 1, ...
int innerIndex = targetPos / outerListSize;
targetList.add(targetPos, outerList.get(outerIndex).get(innerIndex));
}
但这不会为你节省任何东西,因为现在你有一个从 0 运行到 n*n 的循环 - 你仍然有 O(n2)
关于java - 从 Integer java 列表的列表中查找第一个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50156012/