trouver le numéro double avec O (1) l'espace et O (n)

Je résoudre une question leetcodetrouver le numéro double avec O (1) l'espace et O (n)

Étant donné un nums de tableau contenant n + 1 entiers où chaque entier est compris entre 1 et n (y compris), prouver qu'au moins un numéro en double doit exister. Supposons qu'il n'y a qu'un seul numéro en double, trouver le double d'un O (n) et O (1) la complexité de l'espace

class Solution(object): 
    def findDuplicate(self, nums): 
     """ 
     :type nums: List[int] 
     :rtype: int 
     """ 
     xor=0 
     for num in nums: 
      newx=xor^(2**num) 
      if newx<xor: 
       return num 
      else: 
       xor=newx

Je suis la solution acceptée, mais on m'a dit qu'il est ni O (1) ni le temps O (n).

quelqu'un peut s'il vous plaît aidez-moi à comprendre pourquoi?

Source

2017-09-14 Bhanu sri

Ceci est probablement un doublon de [Rechercher répétition dans O (n) et espace constant] (https://stackoverflow.com/questions/9072600/find-repeating-in-on-and-constant-space) et/ou [Comment trouver la complexité temporelle d'un algorithme] (https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) ou [Time complex of power()] (https://stackoverflow.com/questions/5231096/time-complexity-of-power) – Dukeling

Votre solution n'est pas O (1) espace, ce qui signifie: votre espace/mémoire n'est pas constante mais en fonction de l'entrée!

newx=xor^(2**num)

C'est un XOR sur log_2(2**num) = num bits où num est l'un de vos entrées-numéros, ce qui entraîne un résultat peu log_2(2**num) = num.

Donc n=10 = log_2(2^10) = 10 bits, n=100 = log_2(2^100) = 100 bits. Il augmente linéairement (pas constant).

Il est également pas dans O (n) complexité que vous avez:

une boucle extérieure sur tous les numéros de n
- et/non non constant O (1) Intérieures boucle (voir ci-dessus)
- hypothèse: XOR est pas constante en ce qui concerne la représentation binaire d'entrée
  - qui est pas toujours traité comme cela; mais la physique soutiennent cette affirmation (limite Chandrasekhar, vitesse de la lumière, ...)

Source

2017-09-14 14:08:47 sascha

l'ai eue merci, est-ce O (n) temps? –

10 nombres donneront 11 bits, pas 1024 bits. Et 100 numéros seraient 101 bits. La complexité de l'espace est linéaire, non exponentielle. – interjay

10 bits peuvent exprimer 1024 nombres, le nombre de bits n'est pas aussi grand que vous le dites, seul le nombre calculé à xor avec. – maraca

Votre question est en fait difficile de répondre. Généralement, lorsqu'il s'agit de complexités, il existe un modèle de machine supposé. A standard model suppose que les emplacements de mémoire sont de taille log (n) bits lorsque l'entrée est de taille n, et que les opérations arithmétiques sur les nombres de bits log (n) de taille sont O (1).

Dans ce modèle, votre code n'est pas O (1) dans l'espace et O (n) dans le temps. Votre valeur xor a n bits, et cela ne rentre pas dans un emplacement mémoire constant (il faut en fait n/log (n) emplacements mémoire.) De même, ce n'est pas O (n) dans le temps, car les opérations arithmétiques sont sur des nombres plus grands Pour résoudre votre problème dans l'espace O (1) et dans le temps O (n), vous devez vous assurer que vos valeurs ne sont pas trop grandes. les chiffres du tableau, et vous obtiendrez 1^2^3...^n^d où d est le double. Ainsi, vous pouvez XOR 1^2^3^..^n du XOR total du tableau, et de trouver la valeur en double.

def find_duplicate(ns): 
    r = 0 
    for i, n in enumerate(ns): 
     r ^= i^n 
    return r 

print find_duplicate([1, 3, 2, 4, 5, 4, 6])

Ceci est O (1) espace, et O (n) temps depuis r n'utilise jamais plus de bits que n (c'est-à-dire environ ln (n) bits).

Source

2017-09-14 15:05:44

Une autre méthode serait de xor toutes les valeurs et si n n'est pas 2^x-1, x ou le résultat avec n + 1, n + 2, ... jusqu'à ce que vous atteigniez une puissance de 2 moins 1, je pense que ce serait exige moins d'opérations xor, mais n'est pas si élégant. – maraca

Le calcul de xor 1..n semble inefficace. Une autre solution sur le même thème dans n'importe quelle langue avec des nombres suivant l'arithmétique modulaire (comme non signé en C) consiste à ajouter les nombres et ensuite soustraire leur somme (qui est ((unsigned) n) * (n + 1)/2). –

Ce ne sont pas des emplacements de mémoire 'n/log (n)', c'est 'n/k' où' k' est le nombre de bits par emplacement. –

trouver le numéro double avec O (1) l'espace et O (n)

Répondre

Questions connexes