selon l'hypothèse, les nombres inférieurs à un ne sont pas permis et il n'y a pas de doublons, il y a une simple somme d'identité pour cela - la somme des nombres de 1 à m par incréments de 1 est (m * (m + 1)) / 2 . Vous pouvez ensuite faire la somme du tableau et utiliser cette identité.

vous pouvez savoir s'il y a un dupe sous les garanties ci-dessus, plus la garantie aucun nombre est supérieur à m ou inférieur à n (qui peut être vérifié dans O(N) )

l'idée en pseudo-code:

0) début à N = 0

1) Prendre l'élément N-th dans la liste.

2) si elle n'est pas au bon endroit si la liste a été triée, vérifiez où elle devrait être.

3) Si l'endroit où il devrait être a déjà le même numéro, vous avez un dupe-retour vrai

4) sinon, changez les nombres (pour mettre le premier nombre au bon endroit).

5) avec le numéro que vous venez de changer, est-il au bon endroit?

6) Si non, retournez à l'étape deux.

7) sinon, commencez à l'étape 1 avec N = N + 1. Si ce serait après la fin de la liste, vous n'avez pas dupes.

et, oui, qui court dans O(N) bien qu'il puisse ressembler à O(N ^ 2)

Note à tout le monde (matériel collecté de commentaires)

cette solution fonctionne sous la supposition que vous pouvez modifier le tableau, puis utilise le tri Radix en place (qui atteint la vitesse O(N) ).

d'autres mathy-solutions ont été proposées, mais je ne suis pas sûr qu'aucune d'entre elles aient été prouvées. Il y a un tas de sommes qui pourraient être utiles, mais la plupart d'entre eux tombent dans une explosion dans le nombre de bits nécessaires pour représenter la somme, ce qui violera la constante garantie d'espace supplémentaire. J'ai aussi 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 )

nouvel aperçu (Eh bien, plus de réflexions qui n'aident pas à résoudre mais sont intéressants et je vais au lit):

ainsi, il a été mentionné d'utiliser peut-être la somme + somme des carrés. Personne ne savait si ça marchait ou pas, et j'ai réalisé que ça ne devient un problème que lorsque (x + y) = (n + m), tel que le fait 2 + 2 = 1 + 3. Les carrés ont également ce numéro grâce à triples Pythagorean (so 3^2 + 4^2 + 25^2 == 5^2 + 7^2 + 24^2, et la somme des carrés ne fonctionne pas). Si nous utilisons Fermat's last theorem , nous savons que cela ne peut pas se produire pour n^3. Mais nous ne savons pas non plus s'il n'y a pas de x + y + z = n pour cela (sauf si nous le faisons et je ne le sais pas). Donc, aucune garantie que cela, aussi, ne casse pas - et si nous continuez sur cette voie nous manquons rapidement de bits.

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

je dois dire, trouver des contre-exemples est parfois beaucoup plus facile que de prouver des choses! Considérons les séquences suivantes, qui ont toutes un somme 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 trouver aucun exemple de longueur 6 ou moins. Si vous voulez un exemple qui a les valeurs min et max appropriées aussi, essayez celui de la longueur 8:

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

approche la plus Simple (la modification de hazzen de l'idée):

un tableau entier de longueur m contient tous les nombres de n À n+m-1 exactement une fois iff

• chaque élément de réseau est entre n et n+m-1
• il n'y a pas de duplicata

(raison: il n'y a que des valeurs de m dans la plage entière donnée, donc si le tableau contient des valeurs uniques de m dans cette plage, il doit contenir chacune d'elles une fois)

si vous êtes autorisé à modifier le tableau, vous pouvez vérifier les deux en un passage à travers la liste avec une version modifiée de l'idée de l'algorithme de hazzen (il n'est pas nécessaire de faites n'importe quelle 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 = array[i] - n (c'est la position 0-basée du tableau[i] dans un trié tableau avec des valeurs de n À n+m-1)
  3. alors que j n'est pas égal à i
     1. si la liste[i] est égale à la liste [j] = > RETURN FALSE ("duplicate found")
     2. liste d'échange[i] [j]
     3. recalculer j = array [i] - n
• RETURN TRUE

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

en travaillant avec a[i] % a.length au lieu de a[i] vous réduisez le problème à devoir déterminer que vous avez les numéros 0 à a.length - 1 .

nous prenons cette observation pour acquise et essayons de vérifier si le tableau contient [0,m).

trouver le premier noeud qui n'est pas dans sa position correcte, p.ex.

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 de ce numéro dans la où elle devrait . c'est à dire remplacer le 7 par le 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. En relisant notre position actuelle, nous demandons:

" est-ce le bon numéro Pour ici?"

• si ce n'est pas le cas, nous l'échangeons à sa place correcte.
• S'il est au bon endroit, on bouge à droite et on recommence.

suivant cette règle encore une fois, nous obtenons:

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

cela va progressivement construire la liste correctement de gauche à droite, et chaque nombre sera déplacé au plus une fois, et donc C'est O(n).

S'il y a des dupes, nous le remarquerons dès qu'il y a une tentative d'échanger un numéro backwards dans la liste.

pourquoi les autres solutions utilisent-elles une sommation de chaque valeur? Je pense que c'est risqué, parce que quand vous additionnez O(n) articles dans un nombre, vous utilisez techniquement plus que O(1) espace.

méthode plus simple:

Étape 1, Déterminez s'il y a des doublons. Je ne suis pas sûr que ce soit possible dans L'espace O(1). De toute façon, retournez false s'il y a des doublons.

l'Étape 2, itérer sur la liste, de garder trace de la plus bas et "151970920 plus" haut .

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

tout algorithme à un passage nécessite des bits de stockage Omega(n).

supposons au contraire qu'il existe un algorithme à passage unique qui utilise des bits o(n). Comme il ne fait qu'un passage, il doit résumer les premières valeurs de n/2 dans l'espace o(n). Comme il y a C(n,n/2) = 2^thêta(n), Il est possible d'obtenir des ensembles de valeurs n/2 à partir de S = {1,...,n}, Il existe deux ensembles distincts A et B de valeurs n/2 de sorte que l'état de mémoire est le même après les deux. Si A' = S \ A est le " correct" ensemble de valeurs pour compléter Un, puis l'algorithme ne peut pas répondre correctement pour les entrées

A "- Oui

B " - non

puisqu'il ne peut distinguer le premier cas du second.

Q. E. D.

rejetez - moi si je me trompe, mais je pense que nous pouvons déterminer s'il y a des doublons ou ne pas utiliser la variance. Parce que nous connaissons la moyenne à l'avance (n + (m-1)/2 ou quelque chose comme ça) nous pouvons simplement résumer les nombres et le carré de la différence à la moyenne pour voir si la somme correspond à l'équation (mn + m(m-1)/2) et la variance est (0 + 1 + 4 + ... + (m-1)^2) / m. Si la variance ne correspond pas, il est probable que nous ayons un double.

modifier: variance is supposé être (0 + 1 + 4 + ... + [(m-1)/2]^2)*2/m, parce que la moitié des éléments sont inférieurs à la moyenne et l'autre moitié est supérieure à la moyenne.

S'il y a un double, un terme sur l'équation ci-dessus différera de la séquence correcte, même si un autre double annule complètement le changement de moyenne. Ainsi, la fonction retourne true seulement si la somme et la variance correspondent aux valeurs prédéfinies, que nous pouvons calculer à l'avance.

Voici une solution qui fonctionne en temps O(n)

ceci utilise le pseudocode suggéré par Hazzen plus quelques-unes de mes propres idées. Il fonctionne pour les nombres négatifs aussi bien et ne nécessite pas de somme des carrés des trucs.

function testArray($nums, $n, $m) {
    // check the sum. PHP offers this array_sum() method, but it's
    // trivial to write your own. O(n) here.
    if (array_sum($nums) != ($m * ($m + 2 * $n - 1) / 2)) {
        return false;    // checksum failed.
    }
    for ($i = 0; $i < $m; ++$i) {
        // check if the number is in the proper range
        if ($nums[$i] < $n || $nums[$i] >= $n + $m) {
            return false;  // value out of range.
        }

        while (($shouldBe = $nums[$i] - $n) != $i) {
            if ($nums[$shouldBe] == $nums[$i]) {
                return false;    // duplicate
            }
            $temp = $nums[$i];
            $nums[$i] = $nums[$shouldBe];
            $nums[$shouldBe] = $temp;
        }
    }
    return true;    // huzzah!
}

var_dump(testArray(array(1, 2, 3, 4, 5), 1, 5));  // true
var_dump(testArray(array(5, 4, 3, 2, 1), 1, 5));  // true
var_dump(testArray(array(6, 4, 3, 2, 0), 1, 5));  // false - out of range
var_dump(testArray(array(5, 5, 3, 2, 1), 1, 5));  // false - checksum fail
var_dump(testArray(array(5, 4, 3, 2, 5), 1, 5));  // false - dupe
var_dump(testArray(array(-2, -1, 0, 1, 2), -2, 5)); // true

il y a quelque temps, j'ai entendu parler d'un algorithme de tri très intelligent de quelqu'un qui travaillait pour la compagnie de téléphone. Ils ont dû Trier un nombre énorme de numéros de téléphone. Après avoir passé en revue un ensemble de différentes stratégies de tri, ils ont finalement trouvé une solution très élégante: ils ont juste créé un tableau de bits et traité l'offset dans le tableau de bits comme le numéro de téléphone. Ils ont ensuite balayé leur base de données avec un seul passage, changeant le bit pour chaque nombre à 1. Après ça, ils ont balayé à travers le tableau de bits une fois, crachant les numéros de téléphone pour les inscriptions qui avaient le peu élevé.

dans ce sens, je crois que vous pouvez utiliser les données dans le tableau lui-même comme une structure de méta-données pour chercher des doublons. Dans le pire des cas, vous pourriez avoir un tableau séparé, mais je suis presque sûr que vous pouvez utiliser le tableau d'entrée si vous ne vous gênez pas un peu d'échange.

je vais laisser de côté le paramètre n pour le temps être, b / c qui confond juste les choses - ajouter un décalage d'indice est assez facile à faire.

prendre en considération:

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 il fournit un espace constant et peut fournir un vecteur d'attaque différent pour le problème.

si nous voulons O(n), alors en utilisant un tableau d'octets et quelques opérations de bits fournira la vérification de duplication avec un n/32 octets supplémentaires de mémoire utilisée (en supposant 32 bits, bien sûr).

modifier: l'algorithme ci-dessus pourrait être encore amélioré en ajoutant le contrôle de Somme à l'intérieur de la boucle, et de vérifier pour:

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

de cette façon, il échouera rapidement.

en supposant que vous ne connaissez que la longueur du tableau et que vous êtes autorisé à modifier le tableau, il peut être fait dans L'espace O(1) et le temps O(n).

le processus comporte deux étapes simples. 1. "modulo trier" le tableau. [5,3,2,4] => [4,5,2,3] (O(2n)) 2. Vérifier que le voisin de chaque valeur est supérieur à lui-même (modulo) (O (n))

tout dit que vous avez besoin au plus 3 passes à travers le tableau.

le tri modulo est la partie "délicate", mais l'objectif est simple. Prenez chaque valeur dans le tableau et stockez-la à sa propre adresse (longueur modulo). Cela nécessite un passage à travers le tableau, en boucle au-dessus de chaque emplacement "expulsant" sa valeur en l'échangeant à son emplacement correct et en se déplaçant dans la valeur à sa destination. Si jamais vous déplacez dans une valeur qui est congruente à la valeur que vous venez d'expulser, vous avez un duplicate et pouvez sortir tôt. Pire des cas, il est en O(2n).

le contrôle est un passage simple à travers le tableau examiner chaque valeur avec son prochain plus grand voisin. Toujours en O(n).

l'algorithme combiné est O (n)+O (2n) = O (3n) = O(n)

pseudo-code de ma solution:

foreach(values[]) 
  while(values[i] not congruent to i)
    to-be-evicted = values[i]
    evict(values[i])   // swap to its 'proper' location
    if(values[i]%length == to-be-evicted%length)
      return false;  // a 'duplicate' arrived when we evicted that number
  end while
end foreach
foreach(values[])
  if((values[i]+1)%length != values[i+1]%length)
    return false
end foreach

j'ai inclus la validation de principe du code java ci-dessous, ce n'est pas joli, mais il passe tous les tests de l'unité que j'ai fait pour elle. Je les appelle "StraightArray" parce qu'ils correspondent à la main de poker d'un straight (séquence contiguë ignorant costume).

public class StraightArray {    
    static int evict(int[] a, int i) {
        int t = a[i];
        a[i] = a[t%a.length];
        a[t%a.length] = t;
        return t;
    }
    static boolean isStraight(int[] values) {
        for(int i = 0; i < values.length; i++) {
            while(values[i]%values.length != i) {
                int evicted = evict(values, i);
                if(evicted%values.length == values[i]%values.length) {
                    return false;
                }
            }
        }
        for(int i = 0; i < values.length-1; i++) {
            int n = (values[i]%values.length)+1;
            int m = values[(i+1)]%values.length;
            if(n != m) {
                return false;
            }
        }
        return true;
    }
}

Hazzen de l'implémentation de l'algorithme en C

#include<stdio.h>

#define swapxor(a,i,j) a[i]^=a[j];a[j]^=a[i];a[i]^=a[j];

int check_ntom(int a[], int n, int m) {
    int i = 0, j = 0;
    for(i = 0; i < m; i++) {
        if(a[i] < n || a[i] >= n+m) return 0;   //invalid entry
        j = a[i] - n;
        while(j != i) {
            if(a[i]==a[j]) return -1;           //bucket already occupied. Dupe.
            swapxor(a, i, j);                   //faster bitwise swap
            j = a[i] - n;
            if(a[i]>=n+m) return 0;             //[NEW] invalid entry
        }
    }
    return 200;                                 //OK
}

int main() {
    int n=5, m=5;
    int a[] = {6, 5, 7, 9, 8};
    int r = check_ntom(a, n, m);
    printf("%d", r);
    return 0;
}

Edit: modification apportée au code pour éliminer l'accès à la mémoire illégal.

boolean determineContinuousArray(int *arr, int len)
{
    // Suppose the array is like below:
    //int arr[10] = {7,11,14,9,8,100,12,5,13,6};
    //int len = sizeof(arr)/sizeof(int);

    int n = arr[0];

    int *result = new int[len];
    for(int i=0; i< len; i++)
            result[i] = -1;
    for (int i=0; i < len; i++)
    {
            int cur = arr[i];
            int hold ;
            if ( arr[i] < n){
                    n = arr[i];
            }
            while(true){
                    if ( cur - n >= len){
                            cout << "array index out of range: meaning this is not a valid array" << endl;
                            return false;
                    }
                    else if ( result[cur - n] != cur){
                            hold = result[cur - n];
                            result[cur - n] = cur;
                            if (hold == -1) break;
                            cur = hold;

                    }else{
                            cout << "found duplicate number " << cur << endl;
                            return false;
                    }

            }
    }
    cout << "this is a valid array" << endl;
    for(int j=0 ; j< len; j++)
            cout << result[j] << "," ;
    cout << endl;
    return true;
}

def test(a, n, m):
    seen = [False] * m
    for x in a:
        if x < n or x >= n+m:
            return False
        if seen[x-n]:
            return False
        seen[x-n] = True
    return False not in seen

print test([2, 3, 1], 1, 3)
print test([1, 3, 1], 1, 3)
print test([1, 2, 4], 1, 3)

notez que cela ne fait qu'un passage à travers le premier tableau, sans tenir compte de la recherche linéaire impliquée dans not in . :)

j'aurais aussi pu utiliser un python set , mais j'ai opté pour la solution simple où les caractéristiques de performance de set ne doivent pas être considérées.

mise à jour: Smashery a souligné que j'avais mal interprété "quantité constante de mémoire" et cette solution ne résout pas réellement problème.

si vous voulez connaître la somme des nombres [n ... n + m - 1] utilisez simplement cette équation.

var sum = m * (m + 2 * n - 1) / 2;

qui fonctionne pour tout nombre, positif ou négatif, même si n est une décimale.

pourquoi les autres solutions utilisent-elles une sommation de chaque valeur? Je pense que c'est risqué, parce que quand vous additionnez O(n) articles dans un nombre, vous utilisez techniquement plus que O(1) espace.

O (1) indique un espace constant qui ne change pas du nombre de N. Cela n'a pas d'importance si c'est 1 ou 2 variables aussi longtemps que c'est un nombre constant. Pourquoi dites-vous que c'est plus que L'espace O(1)? Si vous calculez la somme de n nombres en l'accumulant dans une variable temporaire, vous utiliseriez exactement 1 variable de toute façon.

commentant dans une réponse parce que le système ne me permet pas encore d'écrire des commentaires.

mise à jour(en réponse aux commentaires): dans cette réponse, je voulais dire O (1) espace partout où "espace" ou "temps" a été omis. Le texte cité fait partie d'une réponse antérieure à laquelle il s'agit d'une réponse.

étant donné que -

Écrire une méthode qui prend un int tableau de taille m ...

je suppose que c'est juste de conclure qu'il n'y est une limite supérieure pour m, égale à la valeur de la plus grande int (2^32, typique). en d'autres termes, même si m n'est pas spécifié comme int, le fait que le tableau ne peut pas avoir de doublons implique qu'il ne peut pas y avoir plus que nombre de valeurs que vous pouvez formulaire de 32 bits, ce qui implique que m est limitée à un int.

si une telle conclusion est acceptable, alors je propose d'utiliser un espace fixe de (2^33 + 2) * 4 octets = 34 359 738 376 octets = 34,4 GO pour traiter tous les cas possibles. (Sans compter l'espace requis par le tableau d'entrée et sa boucle).

bien sûr, pour l'optimisation, je voudrais d'abord prendre en compte m, et allouer seulement le montant réel neededed, (2m+2) * 4 octets.

si cela est acceptable pour la contrainte D'espace O(1) - pour le problème indiqué - alors laissez-moi passer à une proposition algorithmique... :)

Assumptions : tableau de nombres, positifs ou négatifs, aucun supérieur à ce que 4 octets peuvent contenir. Les doublons sont traités. Première valeur peut être valable int. Restreindre m comme ci-dessus.

Première , créer un tableau int de longueur 2m-1, ary , et de fournir trois variables int: gauche , diff , et droit . Un avis qui fait 2m+2...

Deuxième , prendre la première valeur du tableau d'entrée et la copier sur la position m-1 dans le nouveau tableau. Initialise les trois variables.

• set ary [m-1] - nthVal / / n =0
• set gauche = diff = droit = 0

troisième , boucle les valeurs restantes dans le tableau d'entrée et faire la suivante pour chaque itération:

• set diff = nthVal - ary [m-1]
• si ( diff > m-1 + droit || diff < 1-m + gauche ) return false // en dehors des limites
• if ( ary [m-1+ diff ] != null) return false // dupliquer
• set ary [m-1+ diff ] = nthVal
• si ( diff > à gauche ) gauche = diff // limite gauche lié plus loin sur la droite
• si ( diff < droit ) droit = diff // contraint droit lié plus à gauche

j'ai décidé de mettre ce code, et ça a marché.

voici un échantillon de travail en utilisant C#:

public class Program
{
    static bool puzzle(int[] inAry)
    {
        var m = inAry.Count();
        var outAry = new int?[2 * m - 1];
        int diff = 0;
        int left = 0;
        int right = 0;
        outAry[m - 1] = inAry[0];
        for (var i = 1; i < m; i += 1)
        {
            diff = inAry[i] - inAry[0];
            if (diff > m - 1 + right || diff < 1 - m + left) return false;
            if (outAry[m - 1 + diff] != null) return false;
            outAry[m - 1 + diff] = inAry[i];
            if (diff > left) left = diff;
            if (diff < right) right = diff;
        }
        return true;
    }

    static void Main(string[] args)
    {
        var inAry = new int[3]{ 2, 3, 4 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[13] { -3, 5, -1, -2, 9, 8, 2, 3, 0, 6, 4, 7, 1 };
        Console.WriteLine(puzzle(inAry));
        inAry = new int[3] { 21, 31, 41 };
        Console.WriteLine(puzzle(inAry));
        Console.ReadLine();
    }

}

note : ce commentaire est basé sur le texte original de la question (il a été corrigé depuis)

si la question est posée exactement comme écrit ci-dessus (et ce n'est pas seulement une typographie) et pour le tableau de taille n la fonction devrait retourner (Vrai/Faux) si le tableau se compose des nombres 1...n + 1,

... alors la réponse sera toujours fausse parce que le tableau avec tous les nombres 1...n+1 be de taille n+1 et non N. on peut donc répondre à la question dans O(1). :)

Contre-exemple pour la XOR "algorithme 1519110920" .

bool isperm_popopome(int m; int a[m], int m, int  n)
{
  /** O(m) in time (single pass), O(1) in space,
      no restrictions on n,
      no overflow,
      a[] may be readonly
  */
  int even_xor = 0;
  int odd_xor  = 0;

  for (int i = 0; i < m; ++i)
    {
      if (a[i] % 2 == 0) // is even
        even_xor ^= a[i];
      else
        odd_xor ^= a[i];

      const int b = i + n;
      if (b % 2 == 0)    // is even
        even_xor ^= b;
      else
        odd_xor ^= b;
    }

  return (even_xor == 0) && (odd_xor == 0);
}

a version C de pseudo-code de b3

(pour éviter une mauvaise interprétation du pseudo-code)

Contre-exemple: {1, 1, 2, 4, 6, 7, 7} .

int pow_minus_one(int power)
{
  return (power % 2 == 0) ? 1 : -1;
}

int ceil_half(int n)
{
  return n / 2 + (n % 2);
}

bool isperm_b3_3(int m; int a[m], int m, int n)
{
  /**
     O(m) in time (single pass), O(1) in space,
     doesn't use n
     possible overflow in sum
     a[] may be readonly
   */
  int altsum = 0;
  int mina = INT_MAX;
  int maxa = INT_MIN;

  for (int i = 0; i < m; ++i)
    {
      const int v = a[i] - n + 1; // [n, n+m-1] -> [1, m] to deal with n=0
      if (mina > v)
        mina = v;
      if (maxa < v)
        maxa = v;

      altsum += pow_minus_one(v) * v;
    }
  return ((maxa-mina == m-1)
          and ((pow_minus_one(mina + m-1) * ceil_half(mina + m-1)
                - pow_minus_one(mina-1) * ceil_half(mina-1)) == altsum));
}

En Python:

def ispermutation(iterable, m, n):
    """Whether iterable and the range [n, n+m) have the same elements.

       pre-condition: there are no duplicates in the iterable
    """ 
    for i, elem in enumerate(iterable):
        if not n <= elem < n+m:
            return False

    return i == m-1

print(ispermutation([1, 42], 2, 1)    == False)
print(ispermutation(range(10), 10, 0) == True)
print(ispermutation((2, 1, 3), 3, 1)  == True)
print(ispermutation((2, 1, 3), 3, 0)  == False)
print(ispermutation((2, 1, 3), 4, 1)  == False)
print(ispermutation((2, 1, 3), 2, 1)  == False)

c'est O(m) dans le temps et O(1) dans l'espace. Il ne pas prendre en compte les doublons.

alternative solution:

def ispermutation(iterable, m, n): 
    """Same as above.

    pre-condition: assert(len(list(iterable)) == m)
    """
    return all(n <= elem < n+m for elem in iterable)

MA MEILLEURE OPTION ACTUELLE

def uniqueSet( array )
  check_index = 0; 
  check_value = 0; 
  min = array[0];
  array.each_with_index{ |value,index|
         check_index = check_index ^ ( 1 << index );
         check_value = check_value ^ ( 1 << value );
         min = value if value < min
  } 
  check_index =  check_index  << min;
  return check_index == check_value; 
end

O (n) et espace O (1)

j'ai écrit un script pour forcer les combinaisons qui pouvaient échouer et il n'en a pas trouvé. Si vous avez un tableau qui contrevient à cette fonction ne dire. :)

@J. F. Sebastian

N'est pas un véritable algorithme de hachage. Techniquement, c'est un tableau booléen très efficace de valeurs "vues".

ci = 0, cv = 0
[5,4,3]{ 
  i = 0 
  v = 5 
  1 << 0 == 000001
  1 << 5 == 100000
  0 ^ 000001  = 000001
  0 ^ 100000  = 100000

  i = 1
  v = 4 
  1 << 1 == 000010
  1 << 4 == 010000
  000001 ^ 000010  = 000011
  100000 ^ 010000  = 110000 

  i = 2
  v = 3 
  1 << 2 == 000100
  1 << 3 == 001000
  000011 ^ 000100  = 000111
  110000 ^ 001000  = 111000 
}
min = 3 
000111 << 3 == 111000
111000 === 111000

le point de ceci étant principalement que dans le but de" truquer " la plupart des cas problématiques on utilise des doublons pour le faire. Dans ce système, XOR vous pénalise pour avoir utilisé la même valeur deux fois et suppose que vous l'avez fait 0 fois.

Les mises en garde d'être ici bien sûr:

1. la longueur du tableau d'entrée et la valeur maximale du tableau sont limitées par la valeur maximale pour $x dans ( 1 << $x > 0 )

2. l'efficacité ultime dépend de la façon dont votre système sous-jacent met en œuvre les capacités de:

   1. décalage de 1 bit de rang n à droite.
   2. xor 2 registres. (où les "registres" peuvent, selon leur mise en œuvre, s'étendre à plusieurs registres)

   modifier Il est noté que les déclarations ci-dessus semblent déroutantes. En supposant une machine parfaite, où un "entier" est un registre avec Précision infinie, qui peut encore effectuer A ^ b en O (1) Temps.

mais à défaut de ces hypothèses, il faut commencer à se demander la complexité algorithmique des mathématiques simples.

• Quelle est la complexité de 1 = = 1 ? assurément , qui devrait être O(1) chaque fois que le droit?.
• Qu'en est-il de 2^32 == 2^32 .
• O (1)? 2^33 = = 2^33? Maintenant, vous avez une question de taille de registre et le sous-jacent application.
• heureusement XOR et = = peut être fait en parallèle, donc si on suppose une précision infinie et une machine conçue pour faire face avec une précision infinie, il est sûr d'assumer XOR et = = prendre le temps constant quelle que soit leur valeur ( parce que sa largeur infinie, il aura padding infini 0. Évidemment, cela n'existe pas. Mais aussi, changer 000000 à 000100 n'augmente pas l'utilisation de la mémoire.
• encore sur certaines machines , ( 1 << 32 ) << 1 consommera plus de mémoire, mais combien est incertain.