[JAVA] 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. Screen Shot 2019-12-17 at 19.16.20.png

Screen Shot 2019-12-17 at 19.16.39.png Screen Shot 2019-12-17 at 19.16.53.png

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

Screen Shot 2019-12-17 at 19.51.02.png

Test Screen Shot 2019-12-17 at 19.46.59.png

Output Screen Shot 2019-12-17 at 19.47.47.png

Recommended Posts

Gymnastique algorithmique 12
Gymnastique algorithmique 10
Gymnastique algorithmique 3
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 15
Gymnastique algorithmique 16
Gymnastique algorithmique 8
Gymnastique algorithmique 17
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Gymnastique algorithmique 24 sous-ensembles
Gymnastique algorithmique 23 Intervalles de fusion
Gymnastique d'algorithme 20 Supprimer les doublons
Algorithme Gymnastique 21 Cycle LinkedList
Algorithme Gymnastique 24 Tri cyclique
Gymnastique d'algorithme 19 Sous-chaîne sans répétition
Exercice d'algorithme 6
Gymnastique algorithmique 24 Inverser une liste liée
Algorithme Python
Gymnastique d'algorithme 20 paires avec somme cible
Gymnastique algorithmique 22 Mise au carré d'un tableau trié
Gymnastique algorithmique 24 Milieu de la liste liée
Mémorandum Python (algorithme)
Algorithme d'apprentissage du dictionnaire
Algorithme de recherche de chaînes