J'ai cette question:
donné deux listes triées (stockées dans les tableaux) de la taille n, trouvez un O (journal n) algorithme qui calcule le nième élément le plus important de l'union du deux listes.
Je peux voir qu'il y a probablement une astuce ici car elle nécessite le nième élément le plus important et que les tableaux sont également de taille n, mais je ne peux pas comprendre ce que c'est. Je pensais que je pouvais adapter le compte de comptage, cela fonctionnerait-il?
3 Réponses :
Comparer A [N / 2] et B [N / 2]. Si égal, aucun d'entre eux est notre résultat. Une autre condition d'arrêt de cet algorithme est lorsque les deux tableaux sont de taille 1 (initialement ou après plusieurs étapes de récursivité). Dans ce cas, nous choisissons simplement le plus grand des [N / 2] et B [N / 2].
Si un [N / 2]
Si un [N / 2]> B [N / 2], répétez cette procédure récursive pour la seconde moitié de B [] et la première moitié d'un [].
Depuis chaque étape, la taille du problème est divisée par deux (dans le pire des cas), nous obtiendrons O (log n) algorithme.
Développer toujours la taille de la matrice par deux pour que l'index fonctionne correctement uniquement si n est une puissance de deux. Plus correct de choix de choix d'index (pour arbitraire n ) utiliserait la même stratégie pour une matrice, mais en choisissant un indice complémentaire: j = n-i pour un autre.
Comment prendriez-vous prendre soin de l'affaire {1}, {2}?
Ok, je vois ça. Assez évident maintenant vous en parlez. Merci pour votre aide tout le monde.
Comme Nhahtdh mentionné, vous avez eu l'idée principale de la réponse, mais vous devez garder une trace du nombre d'éléments que vous avez rejetés jusqu'à présent pour savoir comment scinder la liste lorsque vous avez des longueurs inégales et enlevez enfin le bon lorsque les listes restantes lorsque les listes restantes. se composent de 1 valeur unique.
La réponse mise à jour clarifie cet algorithme en fonction des suggestions de NHAHTDH et de Rerito.
Toujours Division de la taille de la matrice par 2 œuvres en général . Il n'est pas nécessaire que n soit le pouvoir de deux.
Notez que cela ne fonctionne pas si les tableaux ne sont pas disjoints et que l'Union est une union dans le sens-union.
@Evgeny Kluev Je ne pense pas que cet algorithme fonctionne pour {1, 3, 8, 20, 30, 31} et {2, 4, 6, 21, 29, 32}. Le 6ème numéro le plus grand est 8. Mais l'algorithme comparera 8 et 6 dans sa première étape et continuera à regarder {1,3} et {21,29,32} auquel cas 8 ne sera jamais reconsidéré.
@allenylzhou: Dans votre exemple, la deuxième étape doit traiter des matrices {1, 3, 8} et {21,29,32} (la moitié de la durée de la longueur-6 est définitivement un réseau de longueur-3), donc 8 sera reconsidéré et enfin trouvé . Toujours vos préoccupations sont valables. Je n'ai pas dit comment exactement les index devraient être calculés. Mais dans la mise en œuvre correcte, nous devons le faire très soigneusement, éviter les erreurs hors-tête.
Evgeny Kluev donne une meilleure réponse - la mine était O (n log n) car je ne les ai pas pensés comme étant triés.
Ce que je peux ajouter, c'est vous donner un lien vers une très belle recherche de vidéos expliquant une recherche binaire, gracieuseté de mit:
Mettre 2 trimestre ensemble dans une liste triée prendra O (n).
Il peut choisir de ne pas les concéder et itérer entre les deux. aswell que ceci en termes d'amortissement. Cela dépend de la manière dont vous implémentez cela. Il ne sait pas si les listes contiennent des répétitions qu'ils pourraient. Ce pourrait être que je me trompe encore, peut-être qu'il n'a pas besoin de les concéder du tout.
Je vois maintenant que ma logique était O (n log n), je modifierai mon message pour refléter cela.
@Shokodemon: Vous savez que O (N journal N) est pire que la manière normale de passer à la fois à la fois, ce qui rendait au maximum O (n).
Oui, ma faute de ne pas lire la question assez bien, excuses.
public static void main(String[] args) {
int[] fred = { 60, 5, 7, 3, 20, 3, 44 };
int[] tmp = new int[fred.length];
go(fred, 1, tmp, 3);
}
public static void go(int[] fred, int cnt, int[] tmp, int whatPosition) {
int max = 0;
int currentPosition = 0;
for (int i = 0; i < fred.length; i++) {
if (i == 0)
max = fred[i];
else {
if (fred[i] > max) {
max = fred[i];
currentPosition = i;
}
}
}
System.arraycopy(fred, 0, tmp, 0, fred.length);
tmp[currentPosition] = 0;
cnt++;
if(cnt != whatPosition)
go(tmp, cnt, tmp, whatPosition);
else{
for (int i = 0; i < tmp.length; i++) {
if (i == 0)
max = tmp[i];
else {
if (tmp[i] > max) {
max = tmp[i];
}
}
}
System.out.println(max);
}
}
Comment le syndicat de 2 listes fonctionne-t-il?
Les tableaux sont-ils disjoints? Sinon, je suis sûr que cela ne peut pas être fait ci-dessous
th (n) (et c'est trivial auth (n) )@Gumbo: Si la taille de la matrice est> N et en supposant que "Union de 2 listes" signifie simplement les mettre tous ensemble, nous pouvons toujours réduire la matrice à la taille N (en raison de la propriété triée).
Comment faites-vous cela alors? Je ne vois pas comment cela peut être fait sans trier l'union, ce qui signifie que ce serait O (nlog n)
Vous pouvez obtenir O (n) facilement donné que les deux listes sont initialement triées.
O (n) est la voie naïve: comparez simplement le plus petit élément de 2 liste, avancer le pointeur et compter.Si Les tableaux sont triés et disjoint , alors il pourrait être possible dans
O (log n) (je pense à une recherche binaire). Sinon, pas une chance.@Joe: Pouvez-vous répondre à ma première question? Nous sommes confus si
Union signifie ici un syndicat d'ensemble, qui supprime l'élément en double, ou est-ce simplement mettre 2 listes ensemble?@nhahtdh Union de deux multisets signifie généralement que le plus grand nombre de comptes sont utilisés. Si les comptes sont ajoutés, j'appellerais alors l'opération "Fusionner", pas "(multiiset) Union".
@nhahtdh qui me confondre aussi. Je supposerais des doublons sont inclus.
@Jan Dvorak Pourriez-vous me donner un indice sur la façon dont la recherche binaire pourrait être utilisée?
@Joe avec des doublons, il est pratiquement impossible sous
O (k) pour trouver le k-ème les plus grands. Sans doublons (ou avec une fusion au lieu d'union), il pourrait être possible (mais je n'ai pas d'algorithme concret non plus).@Joe Fondamentalement - recherchez dans les deux listes en parallèle, mais pas par une valeur mais plutôt par une relation (en valeurs et index). Je ne sais pas si c'est un algorithme viable, mais je vais explorer.
@Jan Dvorak, d'accord, certains, je suppose que cela n'inclut pas les doublons. Puis-je peut-être modifier la recherche de fusion ou une recherche binaire pour obtenir ce que je veux?
@Joe: avec duplicata, je peux faire (log n) ^ 2.
@Joe Fusion Sort est
O (k) , mêmetheta (k)@Jandvorak: peut être fait dans O (log (n)) Voir Comment trouver le kth le plus petit élément Dans l'union de deux tableaux triés?
duplicaté possible de Comment comment Pour trouver le kth le plus petit élément de l'union de deux tableaux triés?
@ J.f.sebastian Cette réponse suppose que les tableaux sont disjoints ou que l'Union est une fusion.
@Jandvorak: Je ne vois aucune restriction. Pourriez-vous fournir un contre-exemple?
@ J.f.sebastian
{1,2,3} ⋃ {1,2,3} = {1,2,3} . Le troisième élément le plus gros est1 , mais l'algorithme affirme qu'il est2 , voir le syndicat comme{1,1,2,2,3,3} .@Jandvorak: Donner description dans la question, la deuxième interprétation (sans supprimer des doublons) est la bonne. Bien que le titre soit dû au mot "numéro" au lieu de "élément" est ambigu.