On m'a posé cette question dans une interview.
étant donné que, il y a 3N + 1 chiffres. n de ces chiffres se produisent dans des triplets, seulement 1 se produit une seule fois. Comment trouvons-nous le numéro unique en temps linéaire I.E., O (n)? Les chiffres ne sont pas triés.
Notez que, s'il y avait 2N + 1 chiffres, N dont on se produit par paires, nous pourrions simplement xor tous les numéros de trouver l'unique. L'intervieweur m'a dit que cela puisse être fait par une manipulation de bits.
3 Réponses :
Vous pouvez inventer un fichier xor (appelez-le Ensuite, si vous La complexité n'est pas exactement linéaire, car les conversions de / sur la base 3 nécessitent une durée logarithmique supplémentaire. Toutefois, si la plage de nombres est constante, le temps de conversion est également constant. code sur C ++ (intentionnellement verbeux): xor3 ) fonctionnant dans la base 3 au lieu de la base 2 et prend simplement chaque logit 3Nary Modulo 3 (lorsque vous habituel xor prend 2nary chiffre modulo 2). XOR3 Tous les chiffres (la convertissant en premier) d'abord) de cette façon, vous serez laissé avec le numéro unique (à la base 3 afin que vous puissiez besoin de le convertir).
Pourquoi la conversion en numéro de 3naire? A-t-il un avantage supplémentaire sur la solution de la théorie?
@parvez_bai non, juste la première idée que je suis venue avec une analogie simple avec binaire / 3nary Xor, sa solution est en effet plus facile à mettre en œuvre.
Oh, Dreamzor (ci-dessus) m'a battu.
byte [] oneCount = new byte [32];
int [] test = {1,2,3,1,5,2,9,9,3,1,2,3,9};
for (int n: test) {
for (int bit = 0; bit < 32; bit++) {
if (((n >> bit) & 1) == 1) {
oneCount[bit]++;
oneCount[bit] = (byte)(oneCount[bit] % 3);
}
}
}
int result = 0;
int x = 1;
for (int bit = 0; bit < 32; bit++) {
result += oneCount[bit] * x;
x = x << 1;
}
System.out.print(result);
Looks like while I was coding, others gave the main idea
Qu'est-ce que vous avez essayé jusqu'à présent?
Qu'est-ce que vous interviewiez?
Qu'en est-il des limites de mémoire et de la gamme de chiffres?