我正在寻找以下问题的更好的解决方案(明智的时间和复杂性):
给定的整数列表。首先打印所有第一个元素,然后打印所有第二个元素,依此类推。
示例:{{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/