Algorithme pour déterminer si le tableau contient n ... n + m?

Question

J'ai vu cette question sur Reddit, et il n'y avait pas de solutions positives présenté, et j'ai pensé qu'il serait un parfait question à se poser ici. C'était dans un fil de discussion sur les questions de l'entrevue:

Écrire une méthode qui prend un int tableau de taille m, et renvoie (Vrai/Faux) si le tableau est constitué de chiffres de n...n+m-1, tous les numéros de la plage et seulement les numéros de la plage. Le tableau n'est pas garanti d'être triés. (Par exemple, {2,3,4} serait return true. {1,3,1} serait de retour faux, {1,2,4} serait de retour faux.

Le problème que j'ai eu avec celui-ci, c'est que mon interviewer m'a posé des questions à optimiser (plus rapide O(n), moins de mémoire, etc), au point où il affirmait vous pourriez le faire dans un passage de la matrice à l'aide d'une quantité constante de la mémoire. Jamais pensé que l'un.

Le long avec vos solutions, merci d'indiquer si ils supposent que le tableau contient des éléments uniques. Indiquer également si votre solution suppose que la séquence commence à 1. (J'ai modifié la question légèrement pour permettre à des cas où ça va, 2, 3, 4...)

edit: je suis maintenant d'avis qu'il n'existe pas linéaire dans le temps et de la constance dans l'espace de l'algorithme qui gère les doublons. Quelqu'un peut-il vérifier?

Le double problème se résume à des tests pour voir si le tableau contient des doublons en O(n) le temps, O(1) de l'espace. Si cela peut être fait, vous pouvez tout simplement d'abord le test et si il n'y a pas de doublons exécuter les algorithmes posté. Donc, pouvez-vous tester pour les dupes en O(n) en temps O(1) de l'espace?

Answer 1

Sous l'hypothèse numéros de moins que l'un ne sont pas autorisés et il n'y a pas de doublons, il y a une simple sommation d'identité pour ce - la somme des nombres d' 1 de m par incréments de 1 est (m * (m + 1)) / 2. Vous pouvez alors la somme de la matrice et de l'utilisation de cette identité.

Vous pouvez savoir si il existe un dupe en vertu de la ci-dessus garantit, en plus de la garantie qu'aucun nombre n'est au-dessus de m ou moins de n (ce qui peut être vérifié en O(N))

L'idée en pseudo-code:
0) Commencer à N = 0
1) Prendre la N-ième élément de la liste.
2) Si elle n'est pas à la bonne place si la liste avait été triés, vérifier où il devrait être.
3) Si le lieu où il doit être a déjà le même numéro, vous avez un double - RETURN TRUE
4) Sinon, échanger les numéros (pour mettre le premier nombre dans le bon endroit).
5) Avec le numéro que vous avez juste échangé avec, est-il au bon endroit?
6) Si non, retournez à l'étape deux.
7) dans le cas Contraire, commencez à l'étape un, avec N = N + 1. Si ce serait après la fin de la liste, vous n'avez pas dupes.

Et, oui, qui s'exécute en O(N) bien qu'il puisse ressembler O(N ^ 2)

Note pour tout le monde (des trucs collectées à partir des commentaires)

Cette solution fonctionne sous l'hypothèse que vous pouvez modifier le tableau, puis utilise en lieu Radix sort (qui réalise O(N) de la vitesse).

D'autres mathy-des solutions ont été mises de l'avant, mais je ne suis pas sûr que n'importe quel d'entre eux ont été prouvés. Il y a un tas de sommes qui pourraient être utiles, mais la plupart d'entre eux s'exécuter dans un résumé du nombre de bits nécessaires à la représentation de la somme, qui viole les lois de la constante de l'espace supplémentaire de garantie. Aussi, je ne sais pas si certains d'entre eux sont capables de produire un numéro distinct pour un ensemble donné de nombres. Je pense qu'une somme de carrés peut travail, qui a connu une formule pour le calculer (voir Wolfram s)

Nouvelles idées (bien, plus de de réflexions qui n'aident pas à résoudre le problème, mais sont intéressantes et je vais au lit):

Ainsi, il a été mentionné, peut-être à utiliser sum + somme des carrés. On ne savait pas si cela a fonctionné ou pas, et j'ai réalisé que cela ne devient un problème que lorsque (x + y) = (n + m), comme le fait que 2 + 2 = 1 + 3. Les places ont aussi ce problème grâce à des triplets de Pythagore (donc 3^2 + 4^2 + 25^2 == 5^2 + 7^2 + 24^2, et la somme des carrés ne fonctionne pas). Si nous utilisons le dernier théorème de Fermat, on sait que cela ne peut pas se produire pour n^3. Mais nous ne savons pas non plus si il n'y a pas de x + y + z = n (à moins de faire et je ne sais pas elle). Donc pas de garantir cela, trop, ne pas casser - et si nous continuons dans cette voie, nous rapidement de bits.

Dans ma joie, cependant, j'ai oublié de noter que vous pouvez briser la somme des carrés, mais en faisant ainsi, vous créez une normale somme qui n'est pas valide. Je ne pense pas que vous pouvez faire les deux, mais, comme il a été noté, nous n'avons pas une preuve en soit.

---

Je dois dire, de trouver des contre-exemples est parfois beaucoup plus facile que de prouver des choses! Considérons les séquences suivantes, qui ont toutes un montant de 28 et une somme de carrés de 140:

[1, 2, 3, 4, 5, 6, 7]
[1, 1, 4, 5, 5, 6, 6] 
[2, 2, 3, 3, 4, 7, 7]

Je ne pouvais pas trouver tout de tels exemples de longueur inférieure ou égale à 6. Si vous voulez un exemple que les valeurs min et max aussi, essayez celui-ci de longueur 8:

[1, 3, 3, 4, 4, 5, 8, 8]

---

Approche la plus simple (la modification de hazzen de l'idée):

Un tableau d'entiers de longueur m contient tous les nombres de n à n+m-1 exactement une fois iff

• chaque élément du tableau est entre n et n+m-1
• il n'y a pas de doublons

(Raison: il y a seulement les valeurs de m dans l'intervalle entier, de sorte que si le tableau contient des m valeurs uniques dans cette gamme, il doit contenir chacun d'entre eux une fois)

Si vous êtes autorisé à modifier le tableau, vous pouvez vérifier à la fois en un seul passage à travers la liste avec une version modifiée de hazzen de l'algorithme idée (il n'est pas besoin de faire une sommation):

• Pour tous les indices de tableau i de 0 à m-1 faire
  1. Si tableau[i] < n ou tableau[i] >= n+m => RETURN FALSE ("valeur hors de l'intervalle trouvé")
  2. Calculer j = tableau[i] - n (c'est le 0 de la position de tableau[i] dans une triés tableau avec les valeurs de n à n+m-1)
  3. Alors que j n'est pas égal à i
     1. Si la liste[i] est égal à la liste[j] => RETURN FALSE (en double"trouvé")
     2. Liste d'échange[i] liste[j]
     3. Recalculer j = tableau[i] - n
• RETURN TRUE

Je ne suis pas sûr si la modification du tableau original de chefs d'accusation contre le maximum autorisé de l'espace supplémentaire de O(1), mais si ce n'est pas ce qui devrait être la solution de l'affiche originale voulait.

Answer 2

En travaillant avec des a[i] % a.length au lieu de a[i] vous réduire le problème à avoir besoin de déterminer que vous avez les numéros 0 de a.length - 1.

Nous profitons de cette observation pour acquis et d'essayer de vérifier si le tableau contient [0,m).

Trouver le premier nœud qui n'est pas dans sa position correcte, par exemple

0 1 2 3 7 5 6 8 4 ;     the original dataset (after the renaming we discussed)
        ^
        `---this is position 4 and the 7 shouldn't be here

Swap que le numéro de l'endroit où il devrait être. c'est à dire le swap 7 avec l' 8:

0 1 2 3 8 5 6 7 4 ; 
        |     `--------- 7 is in the right place.
        `--------------- this is now the 'current' position

Maintenant, nous le répétons. Regardant à nouveau notre position actuelle, nous demandons:

"est-ce que le nombre correct pour ici?"

• Si pas, on échange en sa place.
• Si il est au bon endroit, nous déplacer vers la droite et le faire de nouveau.

Suivant cette règle, on obtient:

0 1 2 3 4 5 6 7 8 ;     4 and 8 were just swapped

Cela permettra de construire progressivement la liste correctement à partir de la gauche vers la droite, et chaque numéro sera déplacé plus d'une fois, et c'est donc O(n).

Si il y a des dupes, et nous allons le remarquer comme c'est bientôt, il est une tentative pour remplacer un certain nombre backwards dans la liste.

Answer 3

Pourquoi les autres solutions que d'utiliser une somme de toutes les valeurs? Je pense que c'est risqué, parce que quand vous additionnez O(n) des éléments dans un seul numéro, vous êtes techniquement à l'aide de plus de O(1) de l'espace.

Méthode plus simple:

L'étape 1 de la figure, s'il y a des doublons. Je ne suis pas sûr si cela est possible en O(1) de l'espace. De toute façon, retourne false si il y a des doublons.

L'étape 2, itérer sur la liste, de garder trace de la plus basse et la plus élevée des éléments.

L'étape 3, N'a (plus haut - plus bas) l'égalité des m ? Si oui, retourne true.

Answer 4

Un passe-algorithme nécessite Omega(n) bits de stockage.

Supposons au contraire qu'il existe une seule passe algorithme qui utilise o(n) bits. Parce qu'il ne fait qu'une seule passe, il doit résumer la première n/2 valeurs dans o(n) l'espace. Puisqu'il y a C(n,n/2) = 2^Theta(n) ensembles possibles de n/2 valeurs de S = {1,...,n}, il existe deux ensembles distincts A et B de n/2 valeurs telles que l'état de la mémoire est la même après deux à la fois. Si A' = S \ A est la "bonne" ensemble de valeurs pour compléter Un, puis l'algorithme ne peut pas répondre correctement pour les entrées

Un A' - oui

B A' - pas de

car il ne peut pas distinguer le premier cas de la seconde.

Q. E. D.

Answer 5

Un certain temps en arrière, j'ai entendu parler d'un très habile algorithme de tri de quelqu'un qui a travaillé pour la compagnie de téléphone. Ils avaient pour trier un grand nombre de numéros de téléphone. Après être passé par un tas de différents types de stratégies, ils sont enfin frapper sur un très élégant solution: ils ont juste créé un tableau de bits, et traité le décalage dans le tableau de bits que le numéro de téléphone. Ils ont ensuite balayé par le biais de leur base de données avec un seul passage, en changeant le bit pour chaque nombre de 1. Après cela, ils ont balayé le tableau de bits une fois, crachant les numéros de téléphone pour les inscriptions qui avaient le peu élevé.

Le long de ces lignes, je crois que vous pouvez utiliser les données dans le tableau lui-même comme un méta-structure de données pour rechercher les doublons. Pire des cas, vous pouvez avoir un tableau distinct, mais je suis sûr que vous pouvez utiliser le tableau d'entrée si vous n'avez pas l'esprit un peu de permutation.

Je vais laisser le paramètre n pour le moment, b/c qui confond tout simplement les choses - l'ajout d'un indice de décalage est assez facile à faire.

Considérer:

for i = 0 to m
  if (a[a[i]]==a[i]) return false; // we have a duplicate
  while (a[a[i]] > a[i]) swapArrayIndexes(a[i], i)
  sum = sum + a[i]
next

if sum = (n+m-1)*m return true else return false

Ce n'est pas O(n) - probablement plus proche de O(n Log n) - mais elle n'en continu, de l'espace et peut fournir un autre vecteur d'attaque pour le problème.

Si nous voulons que O(n), puis à l'aide d'un tableau d'octets et de certaines opérations sur les bits fournira la duplication de vérifier avec un supplément n/32 octets de mémoire utilisée (en supposant 32 bits entiers, bien sûr).

EDIT: L'algorithme ci-dessus pourrait être améliorée par l'ajout de la somme de vérifier à l'intérieur de la boucle, et vérifier:

if sum > (n+m-1)*m return false

de cette façon, ce sera un échec rapide.