Gymnastique algorithmique 4

Find the Smallest Common Number À partir des trois tableaux d'entiers triés par ordre croissant, vous devez trouver le plus petit nombre commun aux trois tableaux.

La description

Étant donné trois tableaux d'entiers triés par ** ordre croissant **, implémentez un algorithme qui trouve le plus petit nombre commun aux trois tableaux.

Regardons les trois séquences suivantes. La solution est ** 6 **, le nombre minimum commun à tous les tableaux.

Conseils

1. Profitez des séquences ascendantes.
2. Utilisez trois pointeurs.

Solution Runtime Complexity O(n)

Memory Complexity O(1)

Commentaire

Considérez comment tirer parti du fait que les tableaux sont triés par ordre croissant.

Analysez chaque baie en utilisant trois itérateurs (itérateurs) en même temps. Vous pouvez commencer par analyser le tableau à partir du 0ème index, qui a la valeur minimale pour chaque tableau.

Si les valeurs des index de tableau pointés par les trois itérateurs sont égales Renvoie la valeur minimale qui existe dans tous les tableaux (car les tableaux sont triés par ordre croissant).

Sinon, vérifiez l'itérateur qui pointe vers le plus petit des trois points Il incrémente l'itérateur pour qu'il pointe vers l'index suivant.

Renvoie Null si aucun nombre commun n'est trouvé lorsque l'un des trois itérateurs atteint la fin du tableau.

la mise en oeuvre

Test

Output