Pourquoi mon algorithme O (1) est-il plus complexe?

Question

J'ai résolu ce problème à partir des codesfights:

Note: Ecrivez une solution avec une complexité de temps O (n) et O (1) plus de complexité d'espace, puisque c'est ce que vous devriez faire lors d'une vraie interview.

Étant donné un tableau a qui contient uniquement des nombres compris entre 1 et a.length, recherchez le premier nombre en double dont la deuxième occurrence a l'index minimal. En d'autres termes, s'il y a plus d'un nombre dupliqué, renvoyez le numéro pour lequel la deuxième occurrence a un index plus petit que la deuxième occurrence de l'autre nombre. S'il n'y a pas de tels éléments, retournez -1.

int firstDuplicate(int[] a) { 
    HashSet z = new HashSet(); 
    for (int i: a) { 
     if (z.contains(i)){ 
      return i; 
     } 
     z.add(i); 
    } 
    return -1; 
} 

Ma solution a réussi tous les tests. Cependant, je ne comprends pas comment ma solution a satisfait à l'exigence de complexité supplémentaire O (1). La taille de la hashtable est directement proportionnelle à l'entrée, donc je pense que c'est O (n) complexité de l'espace. Est-ce que les codes ont mal testé mon algorithme ou est-ce que j'ai mal compris quelque chose?

Answer 1

Votre code n'a pas la complexité de l'espace auxiliaire O (1), car ce jeu de hachage peut atteindre la taille n si un tableau de tous les éléments est fourni. Je suppose que l'infrastructure de test en ligne n'a pas vérifié l'utilisation de la mémoire ou n'a pas correctement vérifié l'utilisation de la mémoire. Si vous voulez rencontrer les contraintes d'espace, vous devrez revenir en arrière et essayer de résoudre le problème d'une manière différente.

En guise d'indice, pensez à réorganiser les éléments du tableau.

Answer 2

Ceci est techniquement incorrect, pour deux raisons. Tout d'abord, en fonction des valeurs dans le tableau, il peut y avoir un surcoût lorsque les int s deviennent Integer s et ajoutés au HashSet. Deuxièmement, tandis que la mémoire supplémentaire est en grande partie la surcharge associée à HashSet, cette surcharge est linéairement proportionnelle à la taille de l'ensemble. (Notez que je ne compte pas les éléments, car ils sont déjà présents dans le tableau.)

Habituellement, ces contraintes de mémoire sont testées en définissant une limite à la quantité de mémoire qu'il peut utiliser. Une solution comme celle-ci devrait tomber en dessous de ce seuil.

Answer 3

Si vous êtes en mesure de modifier la matrice entrante, vous pouvez résoudre votre problème avec O(n) complexité de temps, et ne pas utiliser la mémoire externe.

public static int getFirstDuplicate(int... arr) { 
    for (int i = 0; i < arr.length; i++) { 
     int val = Math.abs(arr[i]); 

     if (arr[val - 1] < 0) 
      return val; 
     arr[val - 1] = -arr[val - 1]; 
    } 

    return -1; 
}