高效地比较两个列表并替换和排序

Question

我有两个列表，其中包含一些对象（Fruit类）。我正在使用第三个列表根据以下两个条件添加这些元素。

我希望将第一个列表中的每个对象都添加到第三个列表中。但是，如果在第二个列表中有匹配的对象（基于id和isChecked进行匹配），则我希望将来自第二个列表的对象添加到第三个列表中并忽略第一个列表中的对象。

如果我执行了第一点提到的切换操作，则我希望将该对象移动到第三个列表的第一个元素处。

我已经用下面的代码使其正常工作。但是，我觉得它非常低效。是否有更好的解决方法？

请注意，我无法控制第二个列表，但第一个列表来自Rest端点，我当前将其捕获为列表。不确定是否应该选择Map，请给出建议。

示例：

在下面的示例中，期望的列表输出为[f2，f5，f1，f3，f4]（基于名称）。

这是因为我拥有来自第一个列表的所有元素。 f2和f5在顺序前面，因为它们来自第二个列表（它们匹配了第一个列表中的元素并且isChecked设置为true）。

import lombok.*;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class App {
    public static void main(String[] args) {

        Fruit fruit1 = new Fruit("1", "f1", false);
        Fruit fruit2 = new Fruit("2", "f2", false);
        Fruit fruit3 = new Fruit("3", "f3", false);
        Fruit fruit4 = new Fruit("4", "f4", false);
        Fruit fruit5 = new Fruit("5", "f5", false);

        List<Fruit> firstList = Arrays.asList(fruit1, fruit2, fruit3, fruit4, fruit5);

        Fruit fruit6 = new Fruit("2", "f2", true);
        Fruit fruit7 = new Fruit("7", "f7", false);
        Fruit fruit8 = new Fruit("5", "f5", true);
        Fruit fruit9 = new Fruit("9", "f9", false);
        Fruit fruit10 = new Fruit("10", "f10", false);

        List<Fruit> secondList = Arrays.asList(fruit6, fruit7, fruit8, fruit9, fruit10);

        List<Fruit> finalList = new ArrayList<>();

        // expected list = [f2, f5, f1, f3, f4]

        // this loop is checking and adding objects to finalList.
        // must match the first list and isChecked.
        // in this case, only f6 and f8 matches the first list (id match) and is also 'checked'.
        for (Fruit first : firstList){
            for (Fruit second : secondList){
                if(first.getId().equals(second.getId()) && second.isChecked()){
                    finalList.add(second);
                    break;
                }
            }
        }

        // not done yet. Still need to loop and add back the elements from the first list
        // which were not added in the above loop
        boolean addedFirst = false;
        outer:
        for(Fruit first : firstList){
            for(Fruit finalFruit : finalList){
                if(first.getId().equals(finalFruit.getId())){
                   continue outer;
                }
            }
            finalList.add(first);
        }

        for(Fruit fruit : finalList){
            System.out.println(fruit);
        }
    }
}

@Getter
@Setter
@ToString
class Fruit{
    private String id;
    private String name;
    private boolean isChecked;

    Fruit(String id, String name, boolean isChecked) {
        this.id = id;
        this.name = name;
        this.isChecked = isChecked;
    }
}

- kang

---

在集合框架中使用比较器进行对象比较。 - PrabaharanKathiresan

这看起来像是代码审核，最好在https://codereview.stackexchange.com/发布。 - Joakim Danielson

Answer 1

我的建议是覆盖 Object#equals(java.lang.Object) 方法，用于 Fruit 类。

@Override
public boolean equals(Object obj) {
    if (!(obj instanceof Fruit))
        return false;
    return id.equals(((Fruit)obj).getId());
}

请问翻译的语言是什么？

for (Fruit fruit : firstList) {
    if (secondList.contains(fruit)) {
        int index = secondList.indexOf(fruit);
        fruit = secondList.get(index);
    }
    finalList.add(fruit);
}

为了保持所需的排序顺序 - 先是第二个列表的元素，然后是第二个列表中不匹配的元素 - 可以执行以下操作：

List<Fruit> finalList = new ArrayList<>(secondList);
finalList.retainAll(firstList);
for (Fruit fruit : firstList) {
    if (!finalList.contains(fruit)) 
        finalList.add(fruit);
}

finalList 的顺序现在是 [f2, f5, f1, f3, f4]，这是因为重写了 equals 方法。
请参阅 java.util.List.retainAll()。
每种方法都对每个循环和搜索操作使用线性 O(n) 计算时间，例如 indexOf 和 retainAll。

---

关于这个话题，我认为你想要达到的目标不是很清楚：

f2 和 f5 在顺序中排在前面，因为它们来自第二个列表（它们匹配了第一个列表中的元素，并且将 isChecked 设置为 true）。

如果第一个列表中的 isChecked 被设置为 false，那么会发生什么？第二个列表中的元素是否总是排在第一位，并且保留 isChecked 的顺序，因此基本上您想要在同一个结果列表中进行两种不同类型的排序？

- fantaghirocco

---

第一个列表中的isChecked总是false，只有第二个列表有可能将isChecked设置为true。因此，第二个列表中的元素将首先被推送（根据要求，将添加第一个列表中的所有对象，但如果第二个列表中的对象与第一个列表中的对象匹配并且isChecked=true，则使用第二个列表中的对象，并将其推到顺序上面）。我理解了你的解决方案。仍在思考一个方法来获得0(1)，而不是O(n)，但目前看来这似乎是不可能的。 - kang

Answer 2

我认为你可以使用Map来构建结果列表。它需要额外的O(n)空间和O(n)时间来构建第三个列表。"最初的回答"

public static List<Fruit> buildFinalList(List<Fruit> firstList, List<Fruit> secondList) {
    Map<String, Fruit> map = secondList.stream().collect(Collectors.toMap(Fruit::getId, Function.identity()));

    List<Fruit> finalList = firstList.stream()
                                     .filter(fruit -> map.containsKey(fruit.getId()))
                                     .map(fruit -> map.get(fruit.getId()))
                                     .collect(Collectors.toList());
    firstList.stream()
             .filter(fruit -> !map.containsKey(fruit.getId()))
             .forEach(finalList::add);

    return finalList;
}

---

输出：

Fruit{id='2', name='f2', isChecked=true}
Fruit{id='5', name='f5', isChecked=true}
Fruit{id='1', name='f1', isChecked=false}
Fruit{id='3', name='f3', isChecked=false}
Fruit{id='4', name='f4', isChecked=false}

- oleg.cherednik

---

这个替换功能很好，但是我没有得到顺序，如果我进行了切换，它应该移动到顺序的前面。也就是说，如果我进行了一次切换，它会上移到索引0。如果进行另一个切换，则会上移到索引1，依此类推。 - kang

没问题。可以使用 TreeMap 或 LinkedHashMap 来替代。 - oleg.cherednik

已修复。输出结果与预期不符。 - oleg.cherednik

Answer 3

你可以尝试以下操作：

1. 将第一个列表中的所有项目添加到第三个列表中
2. 比较第二个和第三个列表，并删除共同的项目或条件（请参见Fruit类中的compareTo方法）
3. 如果从第三个列表中删除了项目，则将来自第二个列表的相同项目添加到第三个列表中

请查看下面的代码：

finalList.addAll(firstList);
for (Fruit secondfruit : secondList) {
    boolean isRemoved = finalList.removeIf(firstfruit -> firstfruit.compareTo(secondfruit) == 0);
    if(isRemoved) {
        finalList.add(secondfruit);
    }
}
for (Fruit fruit : finalList) {
    System.out.println(fruit.getName());
}

带有Comparable的水果类，

class Fruit implements Comparable<Fruit> {
    private String id;
    private String name;
    private boolean isChecked;

    @Override
    public int compareTo(Fruit o) {
        if (o.isChecked && this.id.equalsIgnoreCase(o.id)) {
            return 0;
        }
        else {
            return 1;
        }
    }
}

结果为： f1 f3 f4 f2 f5

- PrabaharanKathiresan

---

嗨，我明白你在做什么。但我认为这样做会失去顺序。if(isRemoved) {finalList.add(secondfruit);} 当它应该上升顺序时，它被添加到了列表的末尾。不能添加到索引0，因为该索引处的项可能已经被选中。 - kang

结果应该是 f2，f5，f1，f3，f4。 - kang

Answer 4

假设第一个列表的长度为n，第二个列表的长度为m，你可以花费 O(nlogn) + O(mlogm) +O(n+m) 的时间复杂度来解决这个问题。该算法类似于归并排序。

public static List<Fruit> merge(List<Fruit> list1, List<Fruit> list2) {
    // sort list1 and list2
    Comparator<Fruit> comparator = Comparator.comparingInt(o -> Integer.parseInt(o.getId()));
    Collections.sort(list1, comparator);
    Collections.sort(list2, comparator);

    List<Fruit> finalList1 = new ArrayList<>();
    List<Fruit> finalList2 = new ArrayList<>();
    int length1 = list1.size();
    int length2 = list2.size();
    int index1 = 0;
    int index2 = 0;

    while (index1 < length1 && index2 < length2) {
        Fruit fruit1 = list1.get(index1);
        Fruit fruit2 = list2.get(index2);
        if (fruit1.getId().equals(fruit2.getId()) && fruit2.isChecked()) {
            finalList2.add(fruit2);
            index2++;
            index1++;
        } else {
            finalList1.add(fruit1);
            index1++;
        }
    }

    while (index1 < length1) {
        finalList1.add(list1.get(index1));
        index1++;
    }

    finalList2.addAll(finalList1);
    return finalList2;
}

- TongChen