On m'a posé cette question dans une interview. Bien que l'entretien soit pour la position de Dot Net, il m'a posé cette question dans le contexte de Java, car j'avais mentionné Java également dans mon CV.
Comment trouver l'index d'un élément ayant une valeur x dans un tableau?
J'ai dit itération du premier élément jusqu'à la dernière fois et vérifiez si la valeur est X donnerait le résultat. Il a posé une question sur une méthode impliquant moins de nombre d'itérations, j'ai dit à l'aide de la recherche binaire mais qui n'est possible que pour le tableau trié. J'ai essayé de dire en utilisant l'index de la fonction dans la classe Array. Mais rien de mon côté n'a répondu à cette question.
Y a-t-il un moyen rapide d'obtenir l'index d'un élément ayant une valeur x dans un tableau?
10 Réponses :
Tant qu'il n'y a aucune connaissance de la matrice (est-elle triée? Ascendant ou descendant? etc), il n'y a aucun moyen de trouver un élément sans inspecter chacun.
En outre, c'est exactement ce que indexof fait (lors de l'utilisation des listes).
"... sans inspecter chacun jusqu'à ce que vous le trouviez.", En fait. Si votre élément est le premier, vous n'avez pas besoin d'inspecter chaque élément N le tableau / liste.
Désolé, je pensais que c'était évident! Toute personne qui ne vous dérange pas que dans sa mise en œuvre ne mérite pas de le courir ...
Mais cela ne signifie pas que cela ne pouvait pas être fait plus vite, c'est-à-dire par la parallélisation.
La parrabialisation n'est que potentiellement plus rapide. Si l'article se trouve à proximité du début de la matrice, vous effectuez plus de travail pour parrelaliser la tâche que de commencer à rechercher le tableau. La parrelalisation n'est pas une balle magique qui rend tout ce qui est plus rapide, il vaut mieux pour les grandes tâches, mais il y a un coût des frais généraux qui le rend moins efficace pour les petites tâches.
Puneet - En .NET Son: string[] testArray = { "cat", "dog", "banana", "orange" };
int firstItem = testArray.Select((item, index) => new
{
ItemName = item,
Position = index
}).Where(i => i.ItemName == "banana")
.First()
.Position;
Cette méthode n'existe pas dans Java ... a) Quelle classe de tableau utilisez-vous? b) Les noms de méthodes ne commencent pas avec des lettres majuscules en Java
Il semble que vous n'avez pas lu la question entière, je leur ai demandé d'utiliser la fonction index de l'index, mais ils me demandaient d'écrire la logique moi-même. Ils disaient que la boucle simple que vous avez écrite est correcte, mais cela peut être amélioré et réalisé en moins d'itérations. Pensez-y juste !!!
F1SH - Oups, correct et corrigé ... Puneet - oui, peut voir cela maintenant. Un peu précipité ça un peu !!
@Puneet Dudeja Eh bien, puisque il n'est pas possible de le faire en moins d'itérations, ils voulaient que vous le disiez et expliquez pourquoi. Soit cela ou ils sont tout simplement faux.
C'est fondamentalement le opposé de ce que veut (!); Vous ajoutez simplement plus surcharge (la construction de nombreux nouveaux objets de type anonyme) à ce qui est effectivement toujours la détermination de l'indice d'un élément par dénombrement (en utilisant où / Premier ).
Si une recherche binaire n'est pas possible (Beacuse le tableau n'est pas trié) et vous n'avez pas une sorte d'index de recherche avancé, la seule façon dont je pouvais penser que ce n'est pas O (n ) Si la position de l'élément dans la matrice est une fonction de l'élément lui-même (comme si le tableau est [10, 20, 30, 40] , la position d'un élément < code> n est (n / 10) - 1 ).
Avoir la valeur d'un tableau dépend de son indice est une sorte de tri - au moins vous donne une très bonne idée de la manière dont les éléments sont disposés.
C'est fondamentalement comment fonctionne les tables de hasards.
C'est une question sur les structures et les algorithmes de données (algorithlore une structure de données très simple). Il va au-delà de la langue que vous utilisez.
Si le tableau est commandé, vous pouvez obtenir O (journal N) à l'aide de la recherche binaire et une version modifiée de celle-ci pour les cas de frontière (sans utiliser toujours (A + B) / 2 comme point de pivotement, mais c'est une quirk assez sophistiquée. ).
Si le tableau n'est pas commandé, alors ... bonne chance.
Il peut vous poser des questions sur les méthodes que vous avez pour trouver un article en Java. Mais de toute façon ils ne sont pas plus rapides. Ils peuvent être plus simples d'olny à utiliser (qu'un pour chacun - comparer - retour).
Il existe une autre solution qui crée une structure auxiliaire pour effectuer une recherche plus rapide (comme un hashmap) mais, bien sûr, il est plus coûteux de le créer et de l'utiliser une fois de faire une simple recherche linéaire.
Je pense que vous vouliez dire O (log n) pour un tableau commandé.
Prenez un tableau parfaitement non formé, juste une liste de chiffres en mémoire. Toute la machine peut faire est de regarder des nombres individuels en mémoire et de vérifier s'ils sont le bon nombre. C'est le "problème du biscuit de mot de passe". Il n'y a pas de moyen plus rapide que de rechercher depuis le début jusqu'à ce que la valeur correcte soit touchée.
Êtes-vous sûr de la question? J'ai quelque peu des questions similaires à votre question.
Compte tenu d'un tableau trié, il y a un élément "X" dont la valeur est identique que son index trouver l'index de cet élément. p>
Par exemple: P>
//0,1,2,3,4,5,6,7,8,9, 10
int a[10]={1,3,5,5,6,6,6,8,9,10,11};
Quelle serait une réponse correcte à votre question? Y a-t-il un moyen de faire cela
Autant que je me souvienne, la question était de savoir ce que j'ai demandé ici, car je l'ai confirmé 2 à 3 fois avant de répondre.
Un moyen pratique de la trouver plus rapidement est par traitement parallèle.
Divisez simplement la matrice en n parties et attribuez chaque partie à un fil qui itère à travers les éléments de sa pièce jusqu'à ce que la valeur soit trouvée. N devrait de préférence être le nombre de cœurs du processeur.
Bonne idée. Mais est-il vraiment utile de l'adapter à l'utilisation du noyau du processeur? Le VM ne divise pas le fil de manière égale parmi tous les cœurs ou le fait-il?
Java a le parallélarray (générique) et Parallellongrama (primitif) pour cela. gee.cs.oswego.edu/dl/jsr166/ dist / extra166YDOCS / extra166Y / ... . L'opération est implémentée à l'aide du système N partitions.
@ F1SHSH - En pratique (sous Windows, où la plupart de mes expériences réside), vous trouverez une utilisation de la CPU peut approcher 100% pour tous les noyaux lors de l'utilisation d'un ForkjoinPool dimensionné au nombre de cœurs disponibles. Et cela vous donne également l'avantage d'utiliser davantage de cache L1 qu'avec le boîtier à une seule-thread, qui puisque L1 est généralement dédié à chaque noyau / paire de cœurs.
C'est la responsabilité du VM. En général, l'utilisation de plusieurs threads sur un processeur multicœur doit toujours être plus rapide qu'un seul fil. (Cela ignore les frais généraux de diviser la matrice et de commencer les threads. Le tableau doit bien sûr être suffisamment important pour justifier la parallélisation).
Pour un plus grand parallélisme, vous pouvez toujours affecter le travail à un GPU ou deux: JCuda.de
Cela ressemble à une mauvaise façon d'interviewer les candidats IMHO
@Samuel_xl pourquoi? Quel est le problème avec la question?
Je pense que l'index de la méthode fera également une itération sur la matrice. Ne pensez pas qu'il y ait un tel moyen rapide de le faire.
Si vous pouviez en quelque sorte mettre en oeuvre l'algorithme de grofre en Java, vous pouvez faire mieux. Je suppose que vous avez besoin d'un appel JNI vers l'ordinateur quantique sous-jacent. Non indépendant de la plate-forme.
@emory: Trop de voyage trop chronologique spécifique.
Peut-être voulait-il que vous fassiez un haschmap inversé redondant?