Java - 如何根据第三个列表合并两个列表？

Question

我尝试解决一个问题已经两天了，但我的算法似乎太复杂了。 我需要生成 1 个数据列表，合并 2 个有序列表(下面命名为“列表 A”和“列表 B”) 此合并必须基于引用有序列表来标识每个元素的放置位置。 如果列表 A 和列表 B 包含相同的排名值，我只需要保留其中一个

例如:

Reference list : 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
List A : 2 | 4 | 6
List B : 1 | 4

Expected result : 1 | 2 | 4 | 6

代码

private static List<String> mergeListsUsingRef(final List<String> listRef, final List<String> listA, final List<String> listB) {
    final List<String> res = new ArrayList<>();

    final Iterator<String> listRefIterator = listRef.iterator();
    final Iterator<String> listAIterator = listA.iterator();
    final Iterator<String> listBIterator = listB.iterator();

    String a = listAIterator.hasNext() ? listAIterator.next() : null;
    String b = listBIterator.hasNext() ? listBIterator.next() : null;
    while (listRefIterator.hasNext() && (a != null || b != null)) {
        final String ref = listRefIterator.next();

        if (a != null && ref.equals(a)) {
            res.add(a);

            if (b != null && ref.equals(b)) {
                b = listBIterator.hasNext() ? listBIterator.next() : null;
            }
            a = listAIterator.hasNext() ? listAIterator.next() : null;
        } else if (b != null && ref.equals(b)) {
            res.add(b);

            b = listBIterator.hasNext() ? listBIterator.next() : null;
        }
    }
    return res;
}

现在我必须将最初的问题复杂化。主要困难来自于每个列表中可能多次出现相同的值。 这意味着找出哪些位置允许重复值。

让我们想象一些例子来说明这一点(其中 4 个在引用列表中出现两次)

Reference list : 1 | 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8
List A : 2 | 3 | 5 | 4 | 7
List B : 4 | 7 | 8

Expected result : 2 | 3 | 5 | 4 | 7 | 8

Explaination :
In List A : regarding to reference list, 4 is between 5 and 7 so 4 can be placed only at the second rank
In List B : regarding to reference list, I can't determine where 4 is (first or second rank)
So, List A determine the 4's position at the second rank

<小时/>

Reference list : 1 | 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8
List A : 2 | 3 | 4 | 5 | 7
List B : 4 | 7 | 8

Expected result : 2 | 3 | 4 | 5 | 7 | 8

Explaination :
In List A : regarding to reference list, 4 is between 3 and 5 so 4 can be placed only at the first rank
In List B : regarding to reference list, I can't determine where 4 is (first or second rank)
So, List A determine the 4's position at the first rank

<小时/>

Reference list : 1 | 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8
List A : 2 | 3 | 4 | 5 | 7
List B : 6 | 4 | 7 | 8

Expected result : 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8

Explaination :
In List A : regarding to reference list, 4 is between 3 and 5 so 4 can be placed only at the first rank
In List B : regarding to reference list, 4 is between 6 and 7 so 4 can be placed only at the second rank
So, 4 must be placed at the first and second rank

<小时/>

Reference list : 1 | 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8
List A : 2 | 3 | 4 | 5 | 7
List B : 6 | 7 | 8

Expected result : 2 | 3 | 4 | 5 | 6 | 7 | 8

Explaination :
In List A : regarding to reference list, 4 is between 3 and 5 so 4 can be placed only at the first rank
In List B : 0 occurrence of 4 So, List A determine the 4's position at the first rank

我以前的代码无法处理这些困难的情况。 有谁知道如何帮助我推进其实现？ :)

编辑: 主要 Java 来验证实现:D

public static void main(String[] args) {
System.out.println("EX 1 : ");
        List<String> refList = Arrays.asList("1", "2", "3", "4", "5", "6", "4",
                "7", "8");
        List<String> listA = Arrays.asList("2", "3", "5", "4", "7");
        List<String> listB = Arrays.asList("4", "7", "8");
        List<String> mergeListsUsingRef = mergeListsUsingRef(refList, listA,
                listB);
        System.out.println("Expected : 2 | 3 | 5 | 4 | 7 | 8 ");
        System.out.print("Actual : ");
        for (String res : mergeListsUsingRef) {
            System.out.print(res + " | ");
        }
        System.out.println("");
        System.out.println("----------------------------------");
        System.out.println("EX 2 : ");
        refList = Arrays.asList("1", "2", "3", "4", "5", "6", "4", "7", "8");
        listA = Arrays.asList("2", "3", "4", "5", "7");
        listB = Arrays.asList("4", "7", "8");
        mergeListsUsingRef = mergeListsUsingRef(refList, listA, listB);
        System.out.println("Expected : 2 | 3 | 4 | 5 | 7 | 8 ");
        System.out.print("Actual : ");
        for (String res : mergeListsUsingRef) {
            System.out.print(res + " | ");
        }
        System.out.println("");
        System.out.println("----------------------------------");
        System.out.println("EX 3 : ");
        refList = Arrays.asList("1", "2", "3", "4", "5", "6", "4", "7", "8");
        listA = Arrays.asList("2", "3", "4", "5", "7");
        listB = Arrays.asList("6", "4", "7", "8");
        mergeListsUsingRef = mergeListsUsingRef(refList, listA, listB);
        System.out.println("Expected : 2 | 3 | 4 | 5 | 6 | 4 | 7 | 8 ");
        System.out.print("Actual : ");
        for (String res : mergeListsUsingRef) {
            System.out.print(res + " | ");
        }
        System.out.println("");
        System.out.println("----------------------------------");
        System.out.println("EX 4 : ");
        refList = Arrays.asList("1", "2", "3", "4", "5", "6", "4", "7", "8");
        listA = Arrays.asList("2", "3", "4", "5", "7");
        listB = Arrays.asList("6", "7", "8");
        mergeListsUsingRef = mergeListsUsingRef(refList, listA, listB);
        System.out.println("Expected : 2 | 3 | 4 | 5 | 6 | 7 | 8 ");
        System.out.print("Actual : ");
        for (String res : mergeListsUsingRef) {
            System.out.print(res + " | ");
        }
    }

Answer 1

我认为这个解决方案会起作用 - 它保留列表的顺序，并为上面显示的所有示例提供正确的答案。通过将引用列表保留为索引的 hashMap，如果一个整数可以通过引用出现在另一个整数之前，则可以快速查询任意两个整数。我在 main 中添加了一个打印输出来测试。

 public class ListMergeByRef {

    public Map<Integer, List<Integer>> refMap = new HashMap<Integer,List<Integer>>();
    public ListMergeByRef(List<Integer> reference) {
        int elementIndex = 0;
        for (Integer element:reference) {
            List<Integer> refListPerElement = refMap.get(element);
            if (refListPerElement == null) {
                refListPerElement = new ArrayList<Integer>();
            }
            refListPerElement.add(elementIndex);
            elementIndex++;
            refMap.put(element, refListPerElement);
        }
    }

    public List<Integer> mergeLists (List<Integer> first, List<Integer> second) {
        int firstIndex = 0;
        int secondIndex = 0;
        List<Integer> merged = new ArrayList<Integer>();
        while (firstIndex < first.size() || secondIndex < second.size()) {
            if (firstIndex == first.size()) {
                merged.addAll(second.subList(secondIndex, second.size()));
                return merged;
            } else if (secondIndex == second.size()) {
                merged.addAll(first.subList(firstIndex, first.size()));
                return merged;
            } 

            if (first.get(firstIndex).equals(second.get(secondIndex))){
                merged.add(first.get(firstIndex));
                firstIndex++;
                secondIndex++;
            }
            else if (isElementAllowedBeforeOther(first.get(firstIndex), second.get(secondIndex))) {
                merged.add(first.get(firstIndex));
                firstIndex++;
            } else {
                merged.add(second.get(secondIndex));
                secondIndex++;
            }
        }
        return merged;
    }

    public boolean isElementAllowedBeforeOther(Integer firstElement, Integer secondElement) {
        List<Integer> firstElementIndexes = refMap.get(firstElement);
        List<Integer> secondElementIndexes = refMap.get(secondElement);
        if (firstElementIndexes == null || firstElementIndexes.isEmpty()) return false;
        if (secondElementIndexes == null || secondElementIndexes.isEmpty()) return true;
        if (firstElementIndexes.get(0) < secondElementIndexes.get(secondElementIndexes.size()-1)) return true;
        return false;
    }

    public static void main(String[] args) {
        List<Integer> ref = Arrays.asList(new Integer[] {1,2,3,4,5,6,4,7,8});
        List<Integer> first = Arrays.asList(new Integer[] {2,3,4,5,7});
        List<Integer> second = Arrays.asList(new Integer[] {4,7,8});
        ListMergeByRef merger = new ListMergeByRef(ref);
        List<Integer> mergedList = merger.mergeLists(first, second);
        for (Integer element: mergedList) {
            System.out.print(element+" ");
        }
        System.out.println();
    }