Comparaison de propriétés spécifiques dans les éléments d'un tableau d'objets

Question

J'ai un tableau de Passagers comme suit :

Passenger[] passengers = new Passenger[5];

Voici la définition du terme "passager" :

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

Je veux trouver les passagers dont les propriétés "de" et "à" correspondent ; par exemple, si John a fromID = 3, et Jerry a toID = 3, je peux les rassembler et les ajouter à une liste de passagers. Liste de "pairedPassengers". J'ai déjà une solution O(n^2) comme suit, mais quelle est une méthode plus efficace ?

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

Utilisez un Map pour rechercher un Passenger par leur to domaine. Le site get y put méthodes sur un HashMap sont toutes deux en temps O(1), cet algorithme a donc une complexité globale de 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));
    }
}

Vous devez également écrire un constructeur approprié pour l'objet PairedPassengers classe.

Je suppose ici que chaque passager est censé être jumelé avec un seul autre passager de manière unique, de sorte qu'il n'y ait pas de doublons. to o from champs. S'il y a de tels doublons, il vous faudra alors une Map<Integer, List<Passenger>> pour stocker une liste de passagers avec chaque to valeur. La solution sera toujours en temps O(n) dans le meilleur des cas, mais elle sera O(n²) dans le pire des cas car il peut y avoir un nombre quadratique de paires à trouver.