java - 比较对象数组元素中的特定属性

Question

我有一系列乘客如下:

Passenger[] passengers = new Passenger[5];

这是乘客的定义:

public class Passenger{
    int id;
    int fromId;
    int toId;
}

我想找到“to”和“from”属性匹配的乘客；例如，如果 John 的 fromID = 3，而 Jerry 的 toID = 3，那么我可以将它们放在一起并将它们添加到“pairedPassengers”列表中。我已经有了如下的 O(n^2) 解决方案，但什么是更有效的方法？

public class PairedPassengers{
 int id1;
 int id2;
}

public class MainClass{
 public static void main(String[] args){
    List<PairedPassengers> pairedPassengers = new ArrayList<PairedPassengers>();

    for (int i=0; i<passengers.length(); i++){ //length of the original array with all data
      for (int j=i; j<passengers.length(); j++){
       if (passengers[i].fromId == passengers[j].toId && passengers[i].toId == passengers[j].fromId){
        PairedPassengers pPassengers = new PairedPassengers(); //creating a new object to put pairing passengers into
        pPassengers.id1 = passengers[i].id;
        pPassengers.id2 = passengers[j].id;
        pairedPassengers.add(pPassengers);
       }
      }
    }
 }
}

Answer 1

使用 Map查找 Passenger通过他们的 to field 。 get和 put HashMap 上的方法都是 O(1) 时间，因此该算法的整体复杂度为 O(n)。

Map<Integer, Passenger> to = new HashMap<>();
for(Passenger p : passengers) {
    to.put(p.toId, p);
}

List<PairedPassengers> paired = new ArrayList<>();

for(Passenger q : passengers) {
    Passenger p = to.get(q.fromId);
    if(p != null) {
        paired.add(new PairedPassengers(p, q));
    }
}

您还应该为 PairedPassengers 编写一个合适的构造函数。类(class)。

我在这里假设每个乘客都应该以独特的方式与其他乘客配对，所以没有重复 to或 from领域。如果有这样的重复，那么你将需要一个 Map<Integer, List<Passenger>>存储每个乘客的列表 to值(value)。在最好的情况下，解决方案仍然是 O(n) 时间，但在最坏的情况下它将是 O(n²)，因为可以找到平方数的对。