0

我有两个 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));
                        }
                    }
                }
            }
        }

有人可以帮忙吗？

4

4 回答 4

2

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

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(...)等来进一步优化。还必须添加对空行的处理。

于 2013-03-21T20:28:24.033 回答
1

我通常通过处理来解决这个问题Map。可以使用其他集合，例如列表，但我发现使用地图的代码更易于阅读（并且可能不是性能问题，除非您的列表包含数百万个元素）。

在这种情况下，我将有一个Map<Integer,String>用于保持条目正确顺序的方法。此类地图将作为值存储在另一个地图中，其中键是级别编号。我将TreeMap用作实现类，因为它根据条目的键对条目进行排序。

Map<Integer,Map<Integer,String>> map = new TreeMap<>();
int level=0; //current level
for (String line:templines) {
 if (line.startsWith("==level ")) { 
   level=Integer.valueOf(line.substring(7).replace("==","").trim());
   if (map.get(level)==null) map.put(level,new TreeMap<>());
 } else if (line.length>0) {
   int pos = line.indexOf('.');
   if (pos>0) {
    int n = Integer.valueOf(line.substring(0,pos));
    line=line.substring(pos+1);
    map.get(level).put(n,line); 
   }
 }
}

获得地图后，我将对其进行迭代并将值保存在另一个列表中。

List<String> merged = new ArrayList<String>();
for (Map.Entry<Integer,Map<Integer,String>> entry:map.entrySet()) {
  list.add("==level "+entry.getKey()+"==");
  for (String line:entry.getValue().values()) {
   list.add(line);
  }
}
于 2013-03-21T19:36:09.740 回答
1

基本上，您必须使用 Map 将每个级别作为键并将行列表作为值。处理完要合并的列表后，获取键集并按降序对其进行排序，以便对级别进行排序。然后，您可以使用排序的键/级别开始迭代映射值。将级别添加到 dest 列表中，对实际级别的列表进行排序并将其所有元素也添加到 dest。

这是我想出的：

public class MergeLists {

    private final static String[] list1 = {
        "==level 1==\r\n", 
        "1.1 2\r\n", 
        "\r\n", 
        "\r\n", 
        "==level 2==\r\n", 
        "1.R4 0\r\n", 
        "2.0 2\r\n", 
        "\r\n", 
        "\r\n", 
        "==level 3==\r\n", 
        "3.R3 1\r\n", 
        "4.R5 1"
    };

    private final static String[] list2 = {
        "==level 3==\r\n", 
        "1.null\r\n", 
        "2.null"
    };

    @Test
    public void mergLists() {
        List<List<String>> listList = new ArrayList<>();
        listList.add(Arrays.asList(list1));
        listList.add(Arrays.asList(list2));
        List<String> mergedList = mergLists(listList);
        for(String s : mergedList) {
            System.out.println(s);
        }
    }

    public List<String> mergLists(List<List<String>> listList) {
        List<String> mergedList = new ArrayList<>();
        Map<String, List<String>> levelMap = new HashMap<String, List<String>>();
        for(int j = 0; j < listList.size(); j++) {
            List<String> list = listList.get(j);
            String actLevel = null;
            for(int i = 0; i < list.size(); i++) {
                String line = list.get(i).trim();
                if(isLevel(line)) {
                    actLevel = line;
                } else {
                    if(actLevel != null) {
                        List<String> levelList = levelMap.get(actLevel);
                        if(levelList == null) {
                            levelList = new ArrayList<>();
                            levelMap.put(actLevel, levelList);
                        }
                        levelList.add(line);
                    } else {
                        System.out.println("line " + (i+1) + " in list " + (j+1) + " does not belong to a level.");
                    }
                }
            }
        }

        List<String> sortedLevelList = new ArrayList<>(levelMap.keySet());
        Collections.sort(sortedLevelList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (extractNumberFromLevel(o1) - extractNumberFromLevel(o2));
            }

            private int extractNumberFromLevel(String level) {
                // check that this meets the format of your level entry (assuming "==level n==")
                int r = 0;
                int i = level.indexOf("level");
                if(i != -1) {
                    int j = level.lastIndexOf("==");
                    if(j != -1) {
                        String n = level.substring(i + "level".length(), j).trim();
                        try {
                            r = Integer.parseInt(n);
                        } catch(NumberFormatException e) {
                            // ignore and return 0
                        } 
                    }
                }
                return r;
            }
        });

        for(String level : sortedLevelList) {
            List<String> lineList = levelMap.get(level);
            Collections.sort(lineList, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.trim().length() == 0 ? 1 /* this puts the empty string at the end of the list */ 
                            : (extractNumberFromLine(o1) - extractNumberFromLine(o2));
                }

                private int extractNumberFromLine(String o) {
                    // check that this meets the format of your line entry (assuming "n.1 2")
                    int r = 0;
                    int i = o.indexOf('.');
                    if(i != -1) {
                        String n = o.substring(0, i).trim();
                        try {
                            r = Integer.parseInt(n);
                        } catch(NumberFormatException e) {
                            // ignore and return 0
                        }
                    }
                    return r;
                }
            });

            mergedList.add(level);
            mergedList.addAll(lineList);
        }

        return mergedList;
    }

    private boolean isLevel(String line) {
        // check that this meets the format of your level entry (assuming "==level n==")
        return line.contains("level");
    }
}

输出

==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
于 2013-03-21T20:24:19.083 回答
0

您可以按级别拆分集合并使用 Apache Commons Collections。

Collection a = createCollection();
Collection b = createCollection();

Collection c = CollectionUtils.union(a,b);
于 2013-03-21T19:01:50.060 回答