我正在寻找以下问题的更好的解决方案(明智的时间和复杂性):

给定的整数列表。首先打印所有第一个元素,然后打印所有第二个元素,依此类推。

示例:{{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/

10-14 18:18
查看更多