Comment trouver un nombre qui se produit un nombre impair de fois dans un tableau SORTED en un temps O (n)?

Question

J'ai une question et j'ai essayé de réfléchir encore et encore... mais n'ai rien à ce détachement de la question. Peut-être que je pourrais obtenir du point de vue des autres, pour essayer de le faire fonctionner...

La question est: on nous a donné un tableau TRIÉ, qui se compose d'une collection de valeurs produisent un MÊME nombre de fois, sauf une, qui se produit nombre IMPAIR de fois. Nous avons besoin de trouver la solution dans le journal de n fois.

Il est facile de trouver la solution en O(n) le temps, mais il semble assez difficile à effectuer dans le journal de n fois.

Answer 1

Théorème: Tout algorithme déterministe pour ce problème de sondes Ω(log² n) emplacements de mémoire dans le pire des cas.

La preuve (complètement réécrit dans un style plus formel):

Soit k > 0 un entier impair et soit n = k². Nous décrivons un adversaire qui force (log₂ (k + 1))² = Ω(log² n) des sondes.

Nous appelons le maximum de sous-séquences d'éléments identiques groupes. L'adversaire est possible entrées se composent de longueur k-k segments x₁ x₂ ... x_k. Pour chaque segment x_j, il existe un entier b_j ∈ [0, k] tel que x_j se compose de b_j copies de j - 1, suivie par k - b_j copies de j. Chaque groupe de chevauchement à plus de deux segments, chaque segment de chevauchement à la plupart des deux groupes.

Group boundaries
|   |     |   |   |
 0 0 1 1 1 2 2 3 3
|     |     |     |
Segment boundaries

Partout où il y a une augmentation de deux, nous supposons une double limite par la convention.

Group boundaries
|     ||       |   |
 0 0 0  2 2 2 2 3 3

Revendication: L'emplacement de la j^ème groupe limite (1 ≤ j ≤ k) est déterminée de manière unique par le segment x_j.

La preuve: C'est juste après la ((j - 1) k + b_j)^th emplacement de mémoire, et x_j unique détermine b_j. //

Nous disons que l'algorithme a observé la j^ème groupe limite au cas où les résultats de ses sondes de x_j unique déterminer la valeur de x_j. Par convention, le début et la fin de l'entrée sont toujours observées. Il est possible que l'algorithme unique de déterminer l'emplacement d'un groupe de frontière sans l'observer.

Group boundaries
|   X   |   |     |
 0 0 ? 1 2 2 3 3 3
|     |     |     |
Segment boundaries

Compte tenu de seulement 0 0 ?, l'algorithme ne peut pas dire à coup sûr si ? est un 0 ou un 1. Dans le contexte, cependant, ? doit y avoir un 1, sinon il y aurait trois impair de groupes, et le groupe se limite à X peut être déduite. Ces conclusions pourraient être problématiques pour l'adversaire, mais il s'avère qu'ils ont peut être fait seulement après que le groupe de la limite en question est "hors de propos".

Demande: À un moment donné au cours de l'algorithme d'exécution, de considérer l'ensemble des limites de groupe qu'il a observé. Exactement consécutives paire est bizarre à distance, et l'étrange groupe se trouve entre eux.

La preuve: Tous les autres consécutives paire limites seulement, même des groupes. //

Définir la longueur impaire sous séquence délimitée par les spécial consécutives paire pertinentes de la sous-suite.

Réclamation: Pas de groupe de frontière à l'intérieur de la sous-suite est déterminée de manière unique. Si il y a au moins un de ces limites, alors l'identité de l'étrange groupe n'est pas déterminée de façon unique.

La preuve: Sans perte de généralité, supposons que chaque emplacement de mémoire non dans la sous-suite a été sondé et que chaque segment contenues dans le sous-suite a exactement un emplacement qui n'a pas été sondé. Supposons qu'à la j^ème groupe limite (que l'on appellera B) se trouve à l'intérieur de la sous-suite. Par hypothèse, les sondes à x_j déterminer B de l'emplacement jusqu'à deux années consécutives de possibilités. Nous appelons l'un à l'étrange distance à partir de la gauche aux limites observées impair de la gauche et l'autre impair de la droite. Les deux possibilités, nous travaillons de gauche à droite et de fixer l'emplacement de toutes les intérieurs groupe de frontière ainsi que le groupe à sa gauche est la même. (Nous pouvons le faire car ils ont chacun deux fois de suite les possibilités.) Si B est impair de la gauche, puis le groupe à sa gauche est l'unique étrange groupe. Si B est impair de la droite, puis le dernier groupe dans la sous-suite est l'unique étrange groupe. Les deux sont des entrées valides, alors l'algorithme est déterminée de manière unique ni l'emplacement de B, ni l'étrange groupe. //

Exemple:

Observed group boundaries; relevant subsequence marked by […]
[             ]   |
 0 0 Y 1 1 Z 2 3 3
|     |     |     |
Segment boundaries

Possibility #1: Y=0, Z=2
Possibility #2: Y=1, Z=2
Possibility #3: Y=1, Z=1

Comme conséquence de cette affirmation, l'algorithme, indépendamment de la façon dont il fonctionne, doit étroit pertinents de la sous-suite à un groupe. Par définition, par conséquent, elle doit respecter certaines limites de groupe. L'adversaire a maintenant la simple tâche de garder l'ouvrir autant de possibilités qu'il peut.

À un moment donné au cours de l'algorithme d'exécution, l'adversaire est à l'intérieur commis une possibilité pour chaque emplacement de mémoire à l'extérieur de la sous-suite. Au début, la sous-suite est l'ensemble de l'entrée, donc il n'y a pas d'engagements initiaux. Chaque fois que l'algorithme de sondes d'un ami de l'emplacement de x_j, l'adversaire doit s'engager à l'une des deux valeurs: j - 1 ou j. Si elle peut éviter de laisser la j^ème limite être observé, il choisit une valeur qui laisse au moins la moitié des possibilités restantes (à l'égard de l'observation). Sinon, il choisit de manière à garder au moins la moitié des groupes dans l'intervalle et s'engage valeurs pour les autres.

De cette façon, l'adversaire des forces de l'algorithme d'observer au moins log₂ (k + 1) limites de groupe, et dans l'observation de la j^ème groupe frontière, l'algorithme est forcé de faire au moins log₂ (k + 1) des sondes.

---

Extensions:

Ce résultat s'étend carrément à des algorithmes randomisés par randomisation à l'entrée, en remplacement de "au mieux diminué de moitié" (à partir de l'algorithme de point de vue) avec "au mieux coupées en deux dans l'attente", et l'application de la norme de concentration des inégalités.

Il s'étend également aux cas où aucun groupe ne peut être plus grand que s les copies; en ce cas, la limite inférieure est Ω(log n log s).

Answer 2

Un tableau trié suggère une recherche binaire. Nous devons redéfinir l'égalité et de comparaison. L'égalité des moyens simples d'un nombre impair d'éléments. Nous pouvons faire la comparaison par l'observation de l'index du premier ou le dernier élément du groupe. Le premier élément est un même indice (base 0) avant de l'étrange groupe, et un index impair après l'étrange groupe. On peut trouver le premier et le dernier élément d'un groupe à l'aide de la recherche binaire. Le coût total est O((log N)2).

La PREUVE DE O((log N)2)

  T(2) = 1 //to make the summation nice
  T(N) = log(N) + T(N/2) //log(N) is finding the first/last elements

Pour N=2^k,

T(2^k) = (log 2^k) + T(2^(k-1))
       = (log 2^k) + (log 2^(k-1)) + T(2^(k-2))
       = (log 2^k) + (log 2^(k-1)) + (log 2^(k-2)) + ... + (log 2^2) + 1
       = k + (k-1) + (k-2) + ... + 1
       = k(k+1)/2
       = (k² + k)/2
       = (log(N)² + log(N))/ 2
       = O(log(N)²)

Answer 3

Regardez le centre de l'élément de la matrice. Avec un couple de binaire appropriée des recherches, vous pouvez trouver la première et de sa dernière apparition dans le tableau. E. g., si le milieu de l'élément est 'a', vous avez besoin de trouver i et j comme indiqué ci-dessous:

[* * * * a a a a * * *]
         ^     ^ 
         |     |
         |     |
         i     j

Est - j - i d'un nombre pair? Vous avez terminé! Sinon (et c'est la clé ici), la question à se poser est que j'ai un pair ou un nombre impair? Voyez-vous ce que ce morceau de la connaissance implique? Ensuite, le reste est facile.

Answer 4

Cette réponse est à l'appui de la réponse publiée par "throwawayacct". Il est digne de la bounty. J'ai passé un peu de temps sur cette question et je suis totalement convaincu que sa démonstration est correcte que vous avez besoin Ω(log(n)^2) les requêtes pour trouver le nombre qui se produit d'un nombre impair de fois. Je suis convaincu parce que j'ai fini par recréer exactement le même argument après l'écrémage de sa solution.

Dans la solution, un adversaire crée une entrée pour rendre la vie difficile pour l'algorithme, mais aussi simple pour un homme de l'analyseur. L'entrée se compose de k pages qui ont chacun des k entrées. Le nombre total d'entrées est n = k^2, et il est important que O(log(k)) = O(log(n)) et Ω(log(k)) = Ω(log(n)). Pour faire la saisie, l'adversaire fait une chaîne de caractères de longueur k de la forme 00...011...1, avec le passage à une position arbitraire. Ensuite, chaque symbole dans la chaîne est étendue dans une page de longueur k de la forme aa...abb...b, où lors de la nième page, a=i et b=i+1. La transition sur chaque page est également dans une position arbitraire, sauf que la parité est d'accord avec le symbole que la page a été élargi.

Il est important de comprendre le "adversaire" méthode de l'analyse d'un algorithme dans le pire des cas. L'adversaire répond aux questions à propos de l'algorithme de l'entrée, sans s'engager pour les futures réponses. Les réponses doivent être uniformes, et le jeu est terminé quand l'adversaire a été épinglé assez de recul pour l'algorithme de parvenir à une conclusion.

Avec ce contexte, voici quelques observations:

1) Si vous voulez apprendre la parité d'une transition dans une page en faisant des requêtes dans cette page, vous devez apprendre la position exacte de la transition et vous avez besoin de Ω(log(k)) des requêtes. Toute collection de requêtes restreint le point de transition à un intervalle, et tout intervalle de longueur de plus de 1 a deux parités. Le plus efficace de la recherche pour la transition en de la page d'une recherche binaire.

2) Le plus subtil et le point le plus important: Il y a deux façons de déterminer la parité d'une transition à l'intérieur d'une page spécifique. Vous pouvez soit faire assez de requêtes dans la page pour trouver le passage, ou vous pouvez le déduire de la parité si vous trouvez la même parité à la fois un plus tôt et au plus tard à la page. Il n'y a aucun moyen d'échapper à ce soit-ou. Un ensemble de requêtes restreint le point de transition dans chaque page, pour un certain intervalle de temps. La seule restriction sur les parités vient d'intervalles de longueur 1. Sinon, les points de transition sont libres de bouger pour avoir tout cohérent parités.

3) Dans l'adversaire méthode, il n'y a aucune chance de grèves. Par exemple, supposons que votre première requête dans une page vers une fin au lieu de au milieu. Puisque l'adversaire n'a pas commis d'une réponse, il est libre de mettre la transition sur le côté long.

4) Le résultat final est que vous êtes obligé de sonder directement la parité dans Ω(log(k)) pages, et le travail pour chacun de ces sous-problèmes est également Ω(log(k)).

5) les Choses ne sont pas beaucoup mieux avec un choix au hasard qu'avec la confrontation des choix. Le calcul est plus compliqué, parce que maintenant vous pouvez obtenir partielle de l'information statistique, plutôt qu'une stricte oui, vous savez un de parité ou non, vous ne le connaissez pas. Mais il fait peu de différence. Par exemple, vous pouvez donner à chaque page de longueur k^2, de sorte que, avec une haute probabilité, la première log(k) des requêtes dans chaque page vous dire presque rien au sujet de la parité dans cette page. L'adversaire peut faire des choix au hasard au début et il fonctionne toujours.

Answer 5

Commencez au milieu de la table et de marche arrière jusqu'à ce que vous obtenez une valeur qui est différent de celui qui est au centre. Vérifier si le nombre au-dessus de cette limite est à un pair ou impair index. Si c'est impair, le nombre produisent un nombre impair de fois vers la gauche, afin de renouveler votre recherche entre le début et la limite que vous avez trouvé. Si c'est la même, puis le numéro de la survenue d'un nombre impair de fois doit être plus loin dans le tableau, afin de répéter la recherche dans la moitié droite.

Comme l'a déclaré, il y a une fonction logarithmique et linéaire de la composante. Si vous voulez garder toute la chose logarithmique, au lieu de marcher vers l'arrière dans le tableau à une valeur différente, vous souhaitez utiliser un binaire de recherche à la place. Sauf si vous vous attendez à de nombreuses répétitions d'un même nombre, le binaire de recherche ne peuvent pas être utile si.