Compte tenu d'un tableau de On m'a demandé cela lors d'un entretien d'embauche. Voici ma réponse: le principe du pigeonhole dit qu'il doit y avoir une répétition. J'ai essayé d'utiliser une approche de recherche binaire, alors je l'ai fait dans Matlab, car c'est ce que je sais: alors je soutiens que l'un de ces, Je pensais que c'était une très bonne solution, mais l'intervieweur a laissé entendre que l'on peut faire mieux. Veuillez poster de meilleures solutions que vous connaissez. N + 1 entiers, chacun dans la plage 1 à n , trouve un entier qui est répété. haut ou bot doit être plus grand que n / 2 par le PHP à nouveau. Prenez cette gamme et répétez.
6 Réponses :
Si vous savez qu'il existe exactement un chiffre qui est en double, vous pouvez le trouver en tommant tous et soustrayez la somme des nombres de 1 à N: sinon, sinon, Vous pouvez parcourir le tableau et mettre chaque numéro dans une hache. Si le numéro existe déjà, c'est la duplication. Ceci est également O (n) en supposant que les opérations de hashtable sont O (1). P> ou un événement mieux - pour éviter la haquetable, vous pouvez utiliser un tableau de booléens de taille N: P> int[] P = new int[] { 3, 2, 5, 1, 4, 2 };
bool[] Q = new bool[6];
foreach( var p in P ){
if ( Q[p] ) {
Console.WriteLine("Duplicate: " + p);
break;
}
Q[p] = true;
}
Ce second est plus lent que la solution binaire que je pense.
Pas vraiment. Ceci iTère uniquement sur le tableau une seule fois, tandis que la solution binaire iTère sur certaines parties de la matrice plus d'une fois.
Mais vous devez économiser trop d'informations. Je veux faire mieux dans l'espace et le temps.
Vrai. Mais quand vous dites "plus lent", vous voulez dire temps. Donc, ce n'est pas plus lent! C'est plus rapide, mais prend plus d'espace.
C'est un temps linéaire et un espace linéaire, que est optimal dans le temps. Il est définitivement plus rapide que la solution de recherche binaire dans la question. Il est également optimal, sage sur le temps, bien que l'espace puisse être amélioré comme dans la réponse de Pengone.
Celui-ci prend plus d'espace, mais je vois que c'est mieux que ma réponse. Merci.
@Shreeevatsar: L'espace ne peut être optimisé que si cela ne vous dérange pas de détruire l'entrée. Si nous voulons la préserver, l'utilisation d'un tableau de booléens est moins chère que la copie de la matrice elle-même.
@Matthieu: La réponse de Pengone ne détruit pas l'entrée. Il ne modifie aucun élément de tableau .
@Shreeevatsar: Droite! Je lis trop vite et je pensais qu'il créait la liste en place. Une réponse géniale alors (bien que l'affacturage dans l'effet de la mise en cache puisse le rendre limant à cause des accès aléatoires).
Je ne sais pas comment vous définissez "mieux", mais peut-être que cela se qualifie. Au moins, il est différent de votre solution et des solutions aux questions de la liste liée (jeu de mots destinés).
Si nous faisons un chemin alors ce chemin contient un cycle si et seulement si Démarrez deux particules sur le premier nœud. Laissez la première particule se déplacer à la vitesse de l'unité et laissez la seconde particule se déplacer à une vitesse d'unité deux fois. Ensuite, s'il y a un cycle, la deuxième particule finira par revenir en boucle derrière la première, et éventuellement, ils seront les mêmes. Pourquoi? Eh bien, si vous pensez aux particules comme sur un cercle (qu'ils seront une fois la boucle trouvée), à chaque unité de temps, la deuxième particule obtient une étape dirigée de plus près du premier. Par conséquent, ils doivent éventuellement entrer en collision. Celui qu'ils font, vous avez trouvé une boucle. Pour trouver la valeur répétée, prenez simplement la longueur de la boucle en laissant une particule de rester immobile pendant que l'autre traverse la boucle à nouveau. Puis démarrez les deux particules au démarrage à nouveau, laissez-la déplacer la longueur de la boucle à venir, puis exécutez les deux particules avec une distance constante entre eux jusqu'à ce qu'ils se retiennent au début de la boucle. comme certains Les commentateurs sont scandalisés que je n'incluiez pas tous les détails de la recherche d'une boucle dans une liste liée, le voici maintenant. Aucune promesse que ce n'est pas buggy (c'est un pseudocode Matlab-Esque après tout), mais il devrait au moins expliquer l'idée. ici j'ai commencé à array ^ k [n + 1] = array ^ l [n + 1] pour certains k! = l , c'est-à-dire s'il y a une répétition. La question devient désormais un problème de liste lié à la liste commune qui peut être résolu comme suit. n +1 parce que matry [i] est compris entre 1 et N, donc aucune particule ne sera jamais renvoyée à n + 1 . Cela fait au plus un passage à travers le tableau (mais pas dans l'ordre) et conserve une trace de deux particules (lentes et rapides) et un entier (longueur). L'espace est donc O (1) et le temps est O (n).
Et si Fast saute sur Sale? Cela pourrait continuer pour toujours.
Temps linéaire, espace constant. Toute autre façon de faire ça? Demandé comme ça, c'est en fait une bonne question d'entrevue.
@Daniel: Non, ça ne peut pas. Il s'agit de la technique standard "POINTER CHASSING" pour détecter les cycles dans une liste. Mouvements lents +1 Chaque étape, mouvement rapide +2, si rapide "gains" sur lentement par +1 chaque étape. Il ne peut pas sauter dessus.
@Daniel: Une bonne question, mais pensez à ce qui se passe lorsque la particule rapide arrive derrière le lent. Si le rapide est un pas en arrière, ils se heurtent à la prochaine étape. Si le rapide est deux marches derrière, alors ils entrent en collision en deux étapes. Avoir du sens.
D'accord. Je pense que je l'obtiens. Merci.
C'est un temps linéaire et un espace constant, et peut être prouvé optimal. Vous avez besoin au moins de temps linéaire (vous devez consulter chaque entrée de réseau) et vous avez besoin d'un espace moins constant.
Oui, je pense que tu as raison. J'aime celui la. Y a-t-il un bon endroit pour en savoir plus sur "Pointeur Chasing"?
@Daniel: Vous pouvez rechercher "Algorithme de recherche de cycle de Floyd". Wikipedia a un peu ; Mais Googling pour des termes connexes peut trouver plus de sources. En outre, Algorithme Rho de Pollard est basé sur cela; expositions de cela peut également aider.
Oui, je vois et comprends. tout n'est pas tout . Puisque mon commentaire n'est pas utile pour personne d'autre, je vais le supprimer bientôt. Juste quelques minutes pour que vous puissiez reconnaître, de sorte que vous puissiez supprimer vos réponses aussi. Merci
@fiver je n'ai aucune idée de ce que vous essayez de communiquer, mais j'aimerais souligner qu'avec l'entrée n = 7, matrice = [2,3,4,5,6,7,3,1] Le programme indique que l'élément répété est 3. Et en fait, il donne une sortie précise pour toutes les données que j'ai testées. Avez-vous réellement testé?
@Hobbs: C'est parce que l'auteur le corrigea - maintenant cela fonctionne, mais sa solution originale n'a pas fonctionné, car il ne trouvait pas le début du cycle :) J'attendais au moins un commentaire de lui, mais oh bien .
Je suis désolé de vous énerver - je pense que j'ai déjà appuyé pour cela. J'étais simplement surpris que tant de personnes ayant une grande popularité ne soient pas avéré que la solution était incorrecte. Ce n'était rien contre toi. Mais ce qui me fait chier, c'est que vous n'admettez pas votre réponse n'était pas correct - vous avez supprimé tous vos commentaires (alors je devais faire de même, car les miens étaient des réponses à la vôtre) et corrigé votre ASNWER, comme si rien n'est arrivé. Quoi qu'il en soit, je m'en fiche, dès que la réponse est correcte, ce qui est maintenant, je vais bien. Bonne chance.
@fiver: la solution n'était pas incorrecte à tout moment, juste incomplète. Il a illustré l'idée de base (détection de cycle), qui était suffisante pour quiconque considère assez fort pour compléter l'algorithme. Mais oui, une réponse complète est meilleure, ce qu'elle est maintenant. Peut-être merci à vos commentaires. :-)
Ah, la partie critique commence à l'élément n + 1, car cela ne peut faire partie d'aucun cycle sans duplication «ordinaire» ... très intelligent!
Formidable! Voici une implémentation en Python, avec des tests: Gist.github.com/theicfire/37609E65230DB47FAE9E
J'ai posté une réponse plus simple. Trouver la longueur du cycle n'est pas nécessaire (étape 2, étape 3 dans cette réponse). Ma réponse s'appuie sur le fait que le nœud rencontre , où lent et rapide se rencontre et démarrage noeud les deux sont Même sauts loin du noeud de cycle . Donc, deux pointeurs commençant par Rencontrez le nœud et START NODE se réuniront au noeud de cycle lorsque vous avez avancé à 1x vitesse. Le nœud Cycle est ce que les éléments répétitifs pointent point.
Que diriez-vous de cette simple solution:
Commencez à créer une arborescence de recherche binaire de la matrice. Chaque fois qu'il y a un élément déjà présent, qui est un duplicata pendant que vous insérez dans la BST, stockez cet élément dans un autre éventail d'éléments en double et continuez votre boucle. Nous n'avons même pas besoin de trier le tableau pour trouver les duplicats ici. < / p>
C'est juste mon idée.Je a été posée la même question dans l'une des entretiens et c'était ma réponse.
for(int i=n+1;i!=a[i];i=a[i]); cout<<i;
Cela fonctionne de la même manière que la réponse de @ Pengone, mais c'est plus simple que je crois.
Explication: Cette approche traite la matrice comme graphique de la valeur à l'index algo: i points à index a [i] - 1 (donc valeur 1 points à index 0 ). Il y a au moins 1 numéro répétitif, le graphique sera donc cyclique. Il y a n + 1 éléments et le max est n , donc le dernier nœud a [n + 1] ne fera jamais une partie de cycle mais entrera dans un cycle. Ceci est important car ce dernier nœud est le noeud Démarrer pour Traversal. Notez que si un nœud qui fait partie d'un cycle est utilisé comme Démarrer le noeud avec lent (1x) et rapide (2x) des pointeurs alors ils Rencontrez ce même noeud lui-même qui n'est pas utile. Appelons le nœud convergent comme rencontre le nœud . Si le noeud correspond est k à l'écart du nœud de cycle , le nœud démarrage sera également k s'éloigne du noeud de cycle . Cette logique est la même que la recherche du nœud de cycle dans une liste liée cyclique. Le tableau est traversé un maximum de 3 fois, donc O (n) heure et O (1) espace. 
A [n + 1] ), recherchez le nœud Retour à l'aide de lent (1x) et Fast (2x) Pointeurs.
Nœud de rencontre et de Démarrer le nœud et ils convergent au nœud (le point de numéros de répétition à nœud de cycle ).
Nous utilisons DÉTECTION DE CERTER à résoudre ce problème.
Tout ce que nous devons faire est Voici le code en C ++:
Mais il peut y avoir beaucoup de répétitions, alors je ne pense pas que ces questions sont les mêmes que les miennes. En outre, le tri est vraiment lent. Beaucoup plus lentement que ma réponse.
@Matt balle et d'autres plus près, je pense que nous étions hâtifs. Les deux dupes ne sont pas vraiment les mêmes.
Je suis d'accord; pas la même question. Mérite d'être rouvert.
@Daniel: Par beaucoup de répétitions, vous voulez dire un entier répété plus d'une fois ou plusieurs entiers répétés (éventuellement plus d'une fois)?
Tous les deux. Vous pouvez avoir des chiffres entre 1 et N autant de fois. C'est pourquoi c'est vraiment difficile.
@Daniel: Il n'est pas vrai que la solution de tri est plus lente que votre réponse. (Cela est plus lent que la réponse de Pengone ci-dessous, cependant.) La solution de tri fonctionne dans le temps O (N journal n), tandis que le vôtre peut être n'importe où de Nlogn à N ^ 2 dans le pire des cas, en fonction de votre implémentation «Prenez cette gamme et répéter". Si vous faites déjà un passage à travers la matrice, il est sous-optimal de ne prendre qu'un seul peu d'informations (comme quelle gamme est plus grande), puis tout recommencer. Une "recherche binaire" qui ne fonctionne pas dans O (log n), le temps ne devrait pas vraiment être appelé la recherche binaire.
Liés, peut-être des doublons: • Pourquoi ai-je à la somme pour trouver le numéro répétitif • Algorithme pour trouver deux numéros répétés dans un tableau sans tri
Il me manque des contraintes ici. Je ne vois pas le problème. La vitesse? Mémoire? Trouver
n'importe quel (titre) ou trouveran (première phrase)?Supprimé ma prétention incorrecte que votre algorithme était incorrect: /
@Shreeevatsar: Je pense que c'est O (n journal n) TEMPS: Sa subdivision binaire où l'étape de test se trouve être un O (N) passant à travers tous les éléments qui accumulent 2 totaux. Chaque étape brise un intervalle en 2 intervalles d'environ demi-taille, au moins l'une d'entre eux doit avoir des éléments "trop nombreux" apparaissant dans la matrice. Bien que la recherche se déroule et que l'intervalle que nous considérons devient plus étroite, de plus en plus des éléments visités dans chaque passage ne contribueront pas à totaliser, car ils ne sont pas à la fois des subranges candidates, ce n'est pas trop grave car il n'y aura que de logement ( n) passe de toute façon.
@j_Random_hacker: Oui, si cela est fait correctement, ce sera O (n journal n) heure. Je n'étais pas très sûr de ce qui se passe après le pas mentionné dans la question, j'ai donc dit «n'importe où de Nlogn à N ^ 2». En tout état de cause, la solution simple de tri de la matrice est également O (n journal n), donc ce n'est pas plus rapide.