Bien, nous y voilà...mes excuses à ceux qui attendent une solution plus rapide. Il s'avère que mon professeur était d'avoir un peu de plaisir avec moi et j'ai complètement raté le point de ce qu'il disait.
Je devrais commencer par clarifier ce que je voulais dire par:
il a laissé entendre qu'il y avait une encore plus rapide façon de faire
L'essentiel de notre conversation était: il a dit que mon XOR approche est intéressante, et nous avons parlé pendant un certain temps sur façon dont je suis arrivé à ma solution. Il m'a demandé si je pensais que ma solution est optimale. Je l'ai dit je n'ai (pour les raisons que j'ai mentionné dans ma question). Puis il m'a demandé, "Êtes-vous sûr?" avec un regard sur son visage, je peux seulement décrire comme "sûr". J'ai hésité, mais a dit oui. Il m'a demandé si je pouvais penser à une meilleure façon de le faire. J'étais un peu comme, "Tu veux dire qu'il y a un moyen plus rapide?" mais au lieu de me donner une réponse claire, il m'a dit de penser. J'ai dit que je le ferais.
Alors j'ai pensé à elle, assurez-vous que mon professeur savait quelque chose que j'ignorais. Et après ne vient pas avec quoi que ce soit pour un jour, je suis venu ici.
Ce que mon professeur en réalité je voulais me faire a été de défendre ma solution comme étant optimal, ne pas essayer de trouver une meilleure solution. Comme il l'a dit: la création d'une belle algorithme est la partie la plus facile, le plus dur est de prouver qu'il fonctionne (et que c'est la meilleure). Il pensait que c'était assez drôle que j'ai passé beaucoup de temps à Trouver-Une-Meilleure-Façon de Terre au lieu d'un simple preuve de O(n) qui aurait pris beaucoup moins de temps (nous avons fini par le faire, voir ci-dessous si vous êtes intéressé).
Donc, je suppose, la grande leçon ici. Je vais être accepter Shashank Gupta réponse car je pense qu'il ne parviennent à répondre à la question initiale, même si la question a été entaché d'irrégularités.
Je vais vous laisser là avec un joli petit Python one-liner que j'ai trouvé en tapant la preuve. C'est pas plus efficace, mais je l'aime:
def getUniqueElement(a, b):
return reduce(lambda x, y: x^y, a + b)
Un Très Informelle "Preuve"
Commençons par les deux tableaux de la question, a et b:
int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};
Nous nous contenterons de dire ici que le plus court tableau a longueur n, puis le long de tableau doit avoir la longueur n + 1. La première étape est de prouver linéaire complexité est d'ajouter des tableaux dans un troisième tableau (que nous appellerons c):
int[] c = {6, 5, 6, 3, 4, 2, 5, 7, 6, 6, 2, 3, 4};
qui a une longueur 2n + 1. Pourquoi faire cela? Eh bien, maintenant nous avons un autre problème: trouver l'élément qui se produit d'un nombre impair de fois, en c (à partir d'ici "nombre impair de fois" et "unique" sont prises pour dire la même chose). C'est en fait une assez populaire question d'entrevue et, apparemment, est où mon professeur a eu l'idée pour son problème, alors maintenant ma question a une certaine importance pratique. Hourra!
Imaginons qu'il y est un algorithme plus rapide que O(n), tel que O(log n). Ce que cela signifie, c'est qu'il aura uniquement accès à certains des éléments de l' c. Par exemple, un O(log n) algorithme pourrait seulement avoir à vérifier les journaux(13) ~ 4 des éléments dans notre exemple de tableau pour déterminer l'élément unique. Notre question est, est-ce possible?
D'abord, nous allons voir si nous pouvons en tirer avec la suppression de tous les éléments (par "retrait", je veux dire de ne pas avoir à y accéder). Que diriez-vous si nous enlever 2 éléments, de sorte que notre algorithme vérifie seulement un subarray d' c avec une longueur 2n - 1? C'est toujours linéaire de la complexité, mais si nous pouvons faire cela, alors peut-être que nous pouvons nous améliorer encore plus.
Donc, nous allons choisir deux éléments d' c complètement au hasard de les enlever. Il ya en fait plusieurs choses qui pourraient arriver ici, que je vais résumer en cas:
// Case 1: Remove two identical elements
{6, 5, 6, 3, 4, 2, 5, 7, 2, 3, 4};
// Case 2: Remove the unique element and one other element
{6, 6, 3, 4, 2, 5, 6, 6, 2, 3, 4};
// Case 3: Remove two different elements, neither of which are unique
{6, 5, 6, 4, 2, 5, 7, 6, 6, 3, 4};
Que fait notre tableau ressemble maintenant? Dans le premier cas, 7 est toujours l'élément unique. Dans le second cas, il est un nouvel élément unique, 5. Et dans le troisième cas, il y a maintenant 3 éléments uniques...ouais c'est un désordre total.
Maintenant notre question devient: peut-on déterminer l'élément unique de l' c juste en regardant ce subarray? Dans le premier cas, nous voyons que 7 est l'élément unique de la subarray, mais nous ne pouvons pas être sûr que c'est aussi l'unique élément de l' c; les deux éléments supprimés aurait pu tout aussi bien pu s'7 et 1. Un raisonnement similaire s'applique pour le deuxième cas. Dans le cas 3, avec 3 éléments uniques, nous n'avons aucun moyen de dire à qui deux sont non-unique en c.
Il devient clair que même avec 2n - 1 d'accès, il n'y a pas suffisamment d'informations pour résoudre le problème. Et donc, la solution optimale est linéaire.
Bien sûr, une vraie preuve d'utilisation de l'induction et de ne pas utiliser la preuve par l'exemple, mais je vais laisser ça à quelqu'un d'autre :)
