Java中List<List<Integer>>按列遍历元素 求O(n)时间复杂度最优解

嘿，咱们先把这个问题里的一个常见误解澄清一下：你提到的两层for循环时间复杂度**并不是O(n²)**哦！

核心逻辑：时间复杂度的正确衡量 #

假设你的输入总共有N个元素（比如示例里的6个元素），不管用什么遍历方式，你都必须访问每一个元素一次才能完成打印——这是问题的下限，因为你没法在不处理元素的情况下输出它们。所以最优的时间复杂度必然是O(N)，而你的两层循环其实已经达到了这个复杂度。

为什么你会觉得是O(n²)？可能是把n当成了行数或者列数，但真正的问题规模应该是总元素数N。比如如果有m行k列，总元素数N=mk，两层循环的总执行次数就是mk=N，所以时间复杂度是O(N)，完全符合你的需求。

具体实现示例（Java） #

下面是一个清晰的实现，同时考虑了子列表长度不一致的情况（比如有的子列表比其他短）：

import java.util.List;
import java.util.Arrays;

public class ColumnTraversal {
    public static void main(String[] args) {
        List<List<Integer>> input = Arrays.asList(
            Arrays.asList(1, 2, 3),
            Arrays.asList(5, 4), // 故意让第二个子列表短一列
            Arrays.asList(7, 8, 9)
        );
        
        // 先找到最长子列表的长度，确定需要遍历的列数
        int maxCols = input.stream()
                           .mapToInt(List::size)
                           .max()
                           .orElse(0);
        
        StringBuilder result = new StringBuilder();
        for (int col = 0; col < maxCols; col++) {
            for (List<Integer> row : input) {
                if (col < row.size()) {
                    if (result.length() > 0) {
                        result.append(", ");
                    }
                    result.append(row.get(col));
                }
            }
        }
        
        System.out.println(result.toString());
        // 输出：1, 5, 7, 2, 4, 8, 3, 9
    }
}

有没有“非嵌套循环”的实现？ #

如果你觉得嵌套循环不够直观，也可以用单次循环来实现，但本质上还是要遍历所有元素，时间复杂度依然是O(N)，比如：

// 基于总元素数的单次循环（假设所有子列表长度相同）
List<List<Integer>> input = Arrays.asList(Arrays.asList(1,2,3), Arrays.asList(5,4,6));
int rows = input.size();
int cols = input.get(0).size();
int totalElements = rows * cols;
StringBuilder result = new StringBuilder();

for (int i = 0; i < totalElements; i++) {
    int col = i / rows; // 因为每列有rows个元素，所以i除以rows得到列索引
    int row = i % rows; // 取余得到行索引
    if (result.length() > 0) {
        result.append(", ");
    }
    result.append(input.get(row).get(col));
}

System.out.println(result.toString());
// 输出：1, 5, 2, 4, 3, 6

但这个写法只适合所有子列表长度相同的情况，否则需要额外处理边界，反而不如嵌套循环直观。

总结 #

不存在比O(N)更优的解法，因为处理所有元素是问题的必要条件。你最初的两层循环思路已经是时间最优的了，只是可能对时间复杂度的计算方式有误解。

内容的提问来源于stack exchange，提问作者Chintan