Étant donné deux listes liées d'entiers. On m'a demandé de retourner une liste liée qui contient les éléments non communs. Je sais comment le faire en O (n^2), un moyen de le faire en O (n)?Comment obtenir les éléments rares de deux liste liée?
Si elles ne sont pas triées, alors je ne crois pas qu'il soit possible d'aller mieux que O (n^2). Cependant, vous pouvez faire mieux en les triant ... vous pouvez trier dans un temps raisonnablement rapide, puis obtenir quelque chose comme O (nlogn) (je ne suis pas certain que ce soit ce que ce serait, mais je pense que ça peut être si rapide si vous utilisez le bon algorithme).
Il est possible d'aller mieux que O (n^2). Voir d'autres solutions impliquant la table de hachage. –
Vous pouvez faire un mergesort in-situ sur des listes liées assez rapidement - asymptotiquement dans O (n log n). Donc oui, le tri puis le diffing résoudront ceci dans O (n log n). Si vous n'êtes pas autorisé à modifier les listes d'origine, vous pouvez les copier, c'est-à-dire O (n), donc c'est toujours O (n log n). –
Utilisez une table de hachage. Iterate à travers la première liste chaînée, en entrant les valeurs que vous rencontrez dans une table de hachage.
Effectuez une itération sur la deuxième liste chaînée, en ajoutant tout élément non trouvé dans la table de hachage dans votre liste d'éléments non communs.
Cette solution doit être O (n), en supposant qu'il n'y a pas de collision dans la table de hachage.
créer une nouvelle liste vide. avoir une table de hachage et le remplir avec des éléments des deux listes. complexité n. puis passez en revue chaque liste séquentiellement et, pendant l'itération, placez ces éléments dans la nouvelle liste qui ne sont pas présents dans la table de hachage. complexité n. complexité globale = n
il y aurait aussi une complexité spatiale de n. – PratLee
Est-ce que c'est ce devoir? Si oui, merci de le marquer comme tel. De plus, les listes d'entrées sont-elles triées? – Pace