时间戳

首页 > 解决方案 > 比较对象数组元素中的特定属性

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

问题描述

我有一组乘客如下：

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);
       }
      }
    }
 }
}

标签： javadata-structures

解决方案

使用 a按他们的领域Map查找 a 。a 上的和方法都是 O(1) 时间，因此该算法的总体复杂度为 O(n)。PassengertogetputHashMap

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该类编写一个合适的构造函数。

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

推荐阅读