如何基于较长列表长度遍历两个列表？含场景及低效实现

需要遍历两个列表，无论其中一个列表的元素在另一个列表中是否存在，都要完成处理（比如插入数据库、生成报告）。比如List A长度为6，List B长度为10，或反之，必须覆盖所有元素。

现有低效实现 #

当前的嵌套循环不仅冗余，还存在逻辑错误（内层循环条件误用外层变量），且时间复杂度为O(n*m)，效率很低：

if(listsA.size() > listsB.size()) {
    for(int i = 0; i < listsA.size(); i ++) {
        for(int j = 0; i < listsB.size(); j ++) { // 此处条件错误，应为j < listsB.size()
            //do something
        }
    }
}else if(listsA.size() < listsB.size()) {
    for(int i = 0; i < listsB.size(); i ++) {
        for(int j = 0; i < listsA.size(); j ++) { // 此处条件错误，应为j < listsA.size()
            //do something
        }
    }
}

补充场景示例 #

比如对比两个文件夹的文件并生成报告，即使A文件夹有文件但B没有，或反之，都需要生成对应报告：

for(File brmFile:brmDirectory.listFiles()) {
    for(File bscsFile:bscsDirectory.listFiles()) {
        //do something
    }
}

这种嵌套循环同样会遗漏单侧存在的文件，且效率低下。

问题示例说明 #

比如：

• List A : [Type : Type A, Amount : 5], [Type : Type B, Amount : 10]
• List B : [Type : Type A, Amount : 5], [Type : Type B, Amount : 10], [Type : Type C, Amount : 7]

如果用以下嵌套循环，List B的第三个元素（Type C）会被遗漏——因为List A仅循环2次，每次遍历List B，但不会单独处理B中无匹配的元素：

for(int i = 0; i < listsA.size(); i ++) {
    for(int j = 0; i < listsB.size(); j ++) { // 条件错误，应为j < listsB.size()
        //do something
    }
}

高效解决方案 #

核心思路是用Map优化查找，分三步处理：匹配元素、A独有的元素、B独有的元素，时间复杂度降至O(n+m)：

代码示例（Java） #

假设元素对象有getType()方法作为唯一标识：

import java.util.Map;
import java.util.Set;
import java.util.HashSet;
import java.util.stream.Collectors;

// 1. 将List B转为以Type为键的Map，O(m)时间
Map<String, YourObject> bElementMap = listsB.stream()
    .collect(Collectors.toMap(YourObject::getType, obj -> obj));

Set<String> processedKeys = new HashSet<>();

// 2. 遍历List A，处理匹配元素和A独有的元素，O(n)时间
for (YourObject aObj : listsA) {
    String typeKey = aObj.getType();
    YourObject matchedBObj = bElementMap.get(typeKey);
    
    if (matchedBObj != null) {
        // 处理A和B都存在的元素
        handleBothElements(aObj, matchedBObj);
        processedKeys.add(typeKey);
    } else {
        // 处理仅A存在的元素（比如插入数据库）
        handleOnlyAElement(aObj);
    }
}

// 3. 遍历List B，处理仅B存在的元素，O(m)时间
for (YourObject bObj : listsB) {
    if (!processedKeys.contains(bObj.getType())) {
        // 处理仅B存在的元素（比如插入数据库）
        handleOnlyBElement(bObj);
    }
}

文件夹场景适配 #

对于文件夹文件对比的场景，可将文件名作为键：

import java.io.File;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;
import java.util.Arrays;
import java.util.stream.Collectors;

File[] brmFiles = brmDirectory.listFiles();
File[] bscsFiles = bscsDirectory.listFiles();

// 转存B文件夹文件到Map
Map<String, File> bscsFileMap = Arrays.stream(bscsFiles)
    .collect(Collectors.toMap(File::getName, file -> file));

Set<String> processedFiles = new HashSet<>();

// 处理A文件夹的文件
for (File brmFile : brmFiles) {
    String fileName = brmFile.getName();
    File matchedBscsFile = bscsFileMap.get(fileName);
    
    if (matchedBscsFile != null) {
        // 处理两边都有的文件，生成对比报告
        generateComparisonReport(brmFile, matchedBscsFile);
        processedFiles.add(fileName);
    } else {
        // 处理仅A有的文件，生成单独报告
        generateSingleFileReport(brmFile, "仅在A文件夹存在");
    }
}

// 处理B文件夹中剩余的文件
for (File bscsFile : bscsFiles) {
    if (!processedFiles.contains(bscsFile.getName())) {
        generateSingleFileReport(bscsFile, "仅在B文件夹存在");
    }
}

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