java - 高效的Java列表合并算法

Question

我有两个 Java 列表(与实际类中一样)，每个列表都有一个编号列表和级别的元素，表示为 String 对象。下面的每一行都是列表中的一个单独的字符串。例如，第一个列表可以是:

==level 1==
1.1 2


==level 2==
1.R4 0
2.0 2


==level 3==
3.R3 1
4.R5 1

第二个可能是:

==level 3==
1.null
2.null

每个列表的长度都是任意的，数字后面的值在这里无关紧要。目标是合并匹配级别的列表。例如，上面两个列表的合并将是:

==level 1==
1.1 2


==level 2==
1.R4 0
2.0 2


==level 3==
1.null
2.null
3.R3 1
4.R5 1

两个列表匹配级别的数字永远不会相同，所以不需要检查。我也相信数字将永远是连续的。这是我目前所了解的，但它并未涵盖所有情况，特别是当合并仅发生在关卡的开头或结尾时。看着也很不爽。 tempLines 和 lines 是两个列表。

for(int x=0; x < lines.size();x++){
            for(int y=0; y < tempLines.size();y++){
                if(tempLines.get(y).equals(lines.get(x)) && !(tempLines.get(y).equals("\n"))&& !(lines.get(x).equals("\n"))){
                    int a=y+1;
                    int b=x+1;
                    while(!(tempLines.get(a).equals("\n"))){
                        while(!(lines.get(b).equals("\n"))){
                            if(Integer.valueOf(tempLines.get(a).charAt(0))==(Integer.valueOf(tempLines.get(a).charAt(0))-1))
                                lines.add(b,tempLines.get(a));
                        }
                    }
                }
            }
        }

有人可以帮忙吗？

Answer 1

鉴于您的两个输入列表都按升序排序，您可以使用合并两个排序列表/数组的标准方法。要点是您不需要在算法中有嵌套循环，而是交替遍历两个列表，始终将较低的元素附加到结果并在该列表中前进。这是关于数字和级别之间差异的草图。

int ix_a = 0;
int ix_b = 0;
List<String> result = new ArrayList<String>();
while (ix_a < A.size() || ix_b < B.size()) {

    // No more elements in A => append everything from B to result
    if (ix_a == A.size()) {
        result.add(B.get(ix_b));
        ix_b++;
        continue;
    }

    // No more elements in B => append everything from A to result
    if (ix_b == B.size()) {
        result.add(A.get(ix_a));
        ix_a++;
        continue;
    } 

    // Always append the lower element and advance in that list. 
    // If both lists contain the same element, append this once and advance in both lists
    // Distinguish between levels and numbers here, levels take higher precedence.
    String a = A.get(ix_a);
    String b = B.get(ix_b);
    if (isLevel(a) && isLevel(b)) {
        if (isLowerLevel(a, b)) {
            result.add(a);
            ix_a++;
        } else if (isLowerLevel(b, a)) {
            result.add(b);
            ix_b++;
        } else {
            result.add(a);
            ix_a++;
            ix_b++;
        }
    } else if (isLevel(a)) {
        result.add(b);
        ix_b++;
    } else if (isLevel(b)) {
        result.add(a);
        ix_a++;
    } else {
        if (isLowerNumber(a, b)) {
            result.add(a);
            ix_a++;
        } else if (isLowerNumber(b, a)) {
            result.add(b);
            ix_b++;
        } else {
            result.add(a);
            ix_a++;
            ix_b++;
        }
    }
}

这可以通过省略不必要的重复检查来进一步优化，例如 isLevel(...) 等。还必须添加空行的处理。