有效的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(...)等不必要的重复检查来进一步优化另外的空行的处理已被添加。

Answer 2

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

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

Collection c = CollectionUtils.union(a,b); 

Answer 3

我通常用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); 
    } 
} 

Answer 4

基本上你将不得不使用你把每个级别的关键和线条为值列表的地图。完成处理要合并的列表后，获取密钥集并对其进行降序排序，以便对该级别进行排序。然后，您可以使用排序的键/级别开始迭代地图值。添加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