donné un ensemble non formé E.g.
entrée: sortie: Je cherche une solution en C, mais tout type de pseudocode serait utile ... Peut-on résoudre ce problème dans O (n) où n est la taille définie? A Quelle est la solution la plus efficace
Pour trouver le plus petit entier x qui n'est pas élément de a tel que x doit être supérieur à un entier m ?
a = {7, 3, 4, 1} , m = 5
x = 6
3 Réponses :
Le code Java suivant doit fonctionner pour vous:
public static int findMinNotInArray(int array[], int n) {
int frequency[] = new int[array.length];
if (n < max(array)) {
for (int i = 0; i < array.length; i++) {
if (array[i] > n && array[i] < n + array.length)
frequency[array[i] - (n + 1)]++;
}
for (int i = 0; i < frequency.length; i++) {
if (frequency[i] == 0)
return i + n + 1;
}
return -1;
} else {
return n + 1;
}
}
public static int max(int array[]) {
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
return max;
}
Non; Pour le cas de test de l'OP, cela renvoie -1 au lieu de (correct) 6 .
J'ai édité la réponse s'il vous plaît examiner!
Je pense que l'approche la plus réalisable est de trier la matrice d'abord. Ensuite, vous pouvez effectuer une recherche binaire pour La complexité de cette approche est celle de l'algorithme de tri, qui est de dire O (nlogn) dans la plupart des cas. M , suivie d'une recherche linéaire pour le point suivant où les voisins sont plus d'un à part.
Pourquoi voudriez-vous le trier en premier? Vous pouvez simplement itérer une fois sur le tableau, faire un (si (a [i]
Vous devez prendre en compte, qu'il existe un déficit apparent, qui est rempli que plus tard. Comme ceci: {0, 2, 3, 4, 1} et m = 0. Vous devez en retourner 5 dans ce cas et vous ne voulez pas essayer 1, 2, 3, 4 séquentiellement parce que cela signifierait O (n * N). C'est pourquoi je trierais d'abord.
@Antonroth: Vous devez trouver une valeur pas dans le tableau. Votre approche fonctionnerait pour trouver une valeur qui se trouve dans le tableau.
Ah, d'accord, mal interprété la question. Cela a du sens alors.
J'ai résolu l'utilisation et une array supplémentaire.here 'Len' est la longueur de la matrice.
int findMin(int *arr,int n,int len)
{
int *hash;
if(len==0)
{return -1; //fail
}
hash=(int*)calloc(len,sizeof(int)); //hash function I'm using is f(x)=f(x)-n;
int i;
for(i=0;i<len;i++){
if(arr[i]>n && arr[i]<len+n){ //because max element can't be more than n
hash[arr[i]-n]++;
}
}
i=1;
while(i<len){
if(hash[i]==0)
return len+i;
i++;
}
return len+n+1;
}
calloc (0, len); semble un peu petit.
@wildplasser merci d'avoir souligné. J'ai mis à jour la réponse
si nmemb ou la taille est 0, alors calloc () renvoie NULL ou une valeur de pointeur unique pouvant être transmise ultérieurement à libérer ().
Vous devriez incrémenter «I» dans la boucle 'Alors que' O)
Merci. J'ai mis à jour.
Soigné. Au). Ce shure bat ma solution - +1 pour ça :-)
@Banarun Pouvez-vous réparer le calloc.
@Armin Qu'est-ce qui ne va pas dans ça?
Vous allociez 0 espace pour votre hachage .
J'ai déjà ajouté la condition "si"
Veuillez regarder de plus près calloc (0, len); et cplusplus.com/reference/cstdlib/calloc ; calloc (0, len); vous donne 0 mémoire quel que soit len .
Mis à jour. Désolé, je n'ai jamais utilisé Caloc () avant.