Source: Microsoft Interview Question
Compte tenu d'une matrice triée dans laquelle chaque élément est présent à deux reprises, sauf celui qui est présent unique, nous devons trouver cet élément.
Maintenant une solution standard O (n) consiste à effectuer une liste XOR de liste, qui retournera l'élément nonpliqué (puisque tous les éléments dupliqués annulent.)
est-il possible de résoudre cela plus rapidement si nous savons que la matrice est triée?
3 Réponses :
Oui, vous pouvez utiliser le tri pour réduire la complexité à Étant donné que le tableau est trié, avant l'élément manquant, chaque valeur occupe les taches Vous allez donc au milieu de la matrice, dites index O (journal n) en effectuant une recherche binaire.
2 * k et 2 * k + 1 dans le tableau (en supposant 0 indexation).
h et vérifier l'index h + 1 si h est même, ou h-1 si h est impair. Si l'élément manquant vient plus tard, les valeurs de ces positions sont égales, si elles deviennent auparavant, les valeurs sont différentes. Répéter jusqu'à ce que l'élément manquant soit situé.
C'est brillant. Très bonne réponse!
Et maintenant, vous vous levez pour la réponse que j'ai posté dans mon commentaire il y a 3 minutes. Med me :)
@ H2CO3 Je tapais la réponse pendant que vous commenciez, de grands esprits se ressemblent, n'est-ce pas? Mais vous obtenez des upvotes aussi, à juste titre.
Vous supposez implicitement que les éléments sont consécutifs. Je ne suis pas sûr que cela soit justifié en fonction de la description du problème.
@jerry non, il n'est pas, mais c'est juste diaboliquement brillant :)
@ Jerry N ° Tout ce qui compte, c'est que les éléments sont triés (ne comptent même pas vraiment, tout ce dont nous avons besoin, c'est que les éléments dupliqués sont à côté de l'autre).
@Ziyao sûr qu'il est: Chaque valeur occupe les taches 2 * k et 2 * k + 1 . Ce n'est pas vrai pour, disons, {1,1,5,5,7,10,10} .
@jerry sûr, 5 occupe 2 et 3, 1 occupe 0 et 1.
@jerry Veuillez noter que k n'est pas la valeur, il s'agit simplement de dire que les numéros même sont 2k .
Je suis corrigé, j'ai mal compris k pour être la valeur en question. Je n'ai clairement pas lu le dernier paragraphe assez près. Avoir un +1 :)
@ H2CO3 Maintenant, la question est que vous avez réciproque, ou est-ce que je suis?
@Danielfischer Eh bien, c'est une bonne question. Si vous avancez également, nous pouvons simplement convenir que nous étions également gentils les uns avec les autres;)
@ H2CO3 Pas pour la première fois, je crois, ni pour la dernière fois;)
On dirait que ma question a acheté la fraternité: p
faire une "recherche" binaire (plutôt traverse) sur le tableau, vérifiez les deux voisins, si les deux sont différents de la valeur au milieu, vous avez la solution. Ceci est O (journal n) .
Vous n'avez pas compris la question, je pense!
@Spandan j'ai compris parfaitement.
Oui, le tableau est trié afin que nous puissions appliquer une recherche binaire pour trouver l'élément unique. Voyons le modèle d'occurrence d'un seul élément. Le nombre total d'éléments sera toujours étrange et unique n'arrive qu'à l'index égal
Nombre total de Éléments 9, éléments uniques toujours présents à l'index même.
Lorsque Nombre total d'éléments 11, éléments uniques toujours présents à l'index même. Lorsque Nombre total d'éléments 13, éléments uniques toujours présents à l'index même. Lorsque ci-dessous est le code Python: < / p> (end_index - start_index)% 4 == 0 , l'élément unique est survenant au milieu. 
(find_index - start_index)% 4! = 0 , l'élément unique n'est pas survenu au milieu. 
(find_index - start_index)% 4 == 0 , l'élément unique se produit au milieu également.
Faites une "recherche" binaire (plutôt traverse) sur le tableau, vérifiez les deux voisins, si le bot est différent de la valeur moyenne, vous avez la solution. Ceci est
O (journal n) .@ H2co3 comment ça va? Les voisins n'étaient-ils toujours pas différents?
@Ziyaowei Nopeeeeee! Je ne parle tout simplement pas anglais. Si le tableau est trié (
1 1 2 2 3 4 4 ), un voisin est identique à la valeur centrale.@ H2CO3 supposez-vous que tous les éléments sont consécutifs? Sinon, comment décidez-vous de vérifier si vous voulez vérifier la moitié inférieure ou la moitié élevée?
@ Jerry Trié Array = consécutif!
@jerry euh, je ne comprends pas ça. Pourriez-vous s'il vous plaît élaborer?
@ H2CO3 Je vous demandais si vous supposez qu'il n'y avait aucun numéro sauté (comme dans votre exemple). Basé sur la réponse de Daniel Fiscer, je comprends ce que tu pensais. Je blâme ma maladie :)
@ Jerry Non, je n'étais pas - le "Suis-je présent à deux fois dans le tableau" L'aspect a peu à rien à voir avec la distance d'éléments consécutifs :) La chose est que si le tableau est trié, les éléments égaux sont toujours des voisins - et mon approche (AB) utilise ce fait;)