Deux éléments d'un tableau dont xor est maximale
Donné un tableau d'entiers ,Vous devez trouver deux éléments dont le XOR est maximale.
Il est naïf approche --juste en choisissant chaque élément et xoring avec d'autres éléments, puis de comparer les résultats afin de trouver la paire.
Autre que cela ,Est-il un algorithme efficace?
- Un bon pari est de prendre la plus grande et la plus petite valeur, étant donné la faible valeur de bits sont alors peu de chances de détruire ' le 'bon' haute bits de la valeur élevée au cours de la xor processus.
- a échoué pour arr={8,4,2} réponse est 8^4 et 4 n'est pas plus petit...
- Il va certainement être une paire de nombres, dont l'un a le haut ensemble de bits et l'autre a le réinitialiser.
- Sont de dupliquer des éléments autorisés ou tous les nombres entiers sont uniques?
Vous devez vous connecter pour publier un commentaire.
Je pense que j'ai un temps O(n lg U) algorithme pour cela, où U est le plus grand nombre. L'idée est semblable à user949300, mais avec un peu plus de détail.
L'intuition est comme suit. Lorsque vous êtes XORing deux nombres ensemble, pour obtenir le maximum de valeur, vous voulez avoir un 1 à la position la plus élevée possible, puis de les appariements qui ont un 1 à ce poste, vous voulez une liaison avec un 1 à la prochaine position la plus haute, etc.
Donc l'algorithme est le suivant. Commencer par trouver plus de 1 peu partout dans les numéros (vous pouvez le faire en temps O(n lg U) en faisant O(lg U) par chacun des n nombres). Maintenant, de diviser le tableau en deux parties - l'un des numéros qui ont un 1 dans le peu et le groupe avec 0 dans le peu. Toute solution optimale doit combiner un nombre avec un 1 dans la première place avec un nombre de 0 dans cet endroit, parce que ce serait mettre un bit à 1 aussi haut que possible. Toute autre couplage a un 0 il.
Maintenant, de manière récursive, nous voulons trouver le couplage de nombres à partir de 1 et 0 dans le groupe qui a le plus grand 1 en eux. Pour ce faire, de ces deux groupes, les diviser en quatre groupes:
Si il y a un numéro dans le 11 et 00 groupe ou dans le 10 et 01 groupes, leur XOR serait l'idéal (à partir de 11). Par conséquent, si l'une de ces paires de groupes n'est pas vide, de façon récursive de calcul la solution idéale pour les groupes, puis retourner le maximum de ces subproblem solutions. Sinon, si les deux groupes sont vides, ce qui signifie que tous les chiffres doivent avoir le même chiffre dans leur deuxième position. Par conséquent, la meilleure XOR d'un numéro 1 et un numéro commençant par 0 finalement la seconde suivante bits annuler, nous devrions donc il suffit de regarder la troisième bit.
Cela donne la suite algorithme récursif qui, commençant avec les deux groupes de chiffres séparées par leur MSB, donne la réponse:
Pour commencer l'algorithme, vous pouvez en fait juste la partition de l'un des numéros du groupe initial en deux groupes - les numéros avec l'ESM 1 et des nombres avec le MSB 0. Vous alors de déclencher un appel récursif de l'algorithme ci-dessus avec les deux groupes de nombres.
Considérez, par exemple, les numéros 5 1 4 3 0 2. Ces représentations
Nous commençons par découper dans le 1 et le 0 groupe:
Maintenant, nous appliquons l'algorithme ci-dessus. Nous nous sommes répartis en groupes de 11, 10, 01, 00:
Maintenant, nous ne pouvons pas paire tout de 11 éléments, avec 00 éléments, afin que nous venons de manière récursive sur les 10 et 01 groupes. Cela signifie que nous avons de construire 100, 101, 010 et 011 groupes:
Maintenant que nous en sommes à seaux avec juste un élément en eux, il nous suffit de vérifier les paires 101 et 010 (qui donne 111) et 100 011 (qui donne 111). L'option fonctionne ici, nous obtenons donc, la meilleure réponse est 7.
Nous allons réfléchir sur le temps d'exécution de cet algorithme. Notez que le maximum de la profondeur de récursion est O(lg U), il n'y a que O(log U) bits dans les chiffres. À chaque niveau de l'arborescence, chaque numéro s'affiche dans exactement un appel récursif, et chacun des appels récursifs ne fonctionne proportionnelle au nombre total de nombres 0 et 1 groupes, parce que nous avons besoin de les distribuer par leurs bits. Par conséquent, il y a O(log U) les niveaux de la récursivité de l'arbre, et chaque niveau ne O(n) de travail, ce qui donne un total de travail de O(n log U).
Espérons que cette aide! Ce était un jeu génial de problème!
Ignorer le bit de signe, l'une des valeurs doit être l'une des valeurs les plus importantes ensemble de bits. À moins que toutes les valeurs ont que peu ensemble, dans ce cas, vous allez à la prochaine plus haute de bits significatifs qui n'est pas défini dans toutes les valeurs. Donc, vous pourriez réduire les possibilités pour la 1ère valeur en regardant le TSL. Par exemple, si les possibilités sont
La 1ère valeur de la max la paire doit être 0x100000 ou 0x10ABCD.
@Erreur interne du Serveur, je ne pense pas que la plus petite est nécessairement correcte. Je n'ai pas une grande idée pour éplucher la 2ème valeur. Juste toute valeur n'est pas dans la liste des possibles 1er valeurs. Dans mon exemple, 0x001ABC ou 0x000ABC.
Cela peut être résolu en
O(NlogN)
temps de la complexité en utilisant Trie.arr[i]
élément dearr[0, 1, ..... N]
arr[i]
. Nous savons xor de différents types de bits(0 ^ 1
ou1 ^ 0
) est toujours1
. Donc, lors de la requête pour chaque bit, essayez de traverser le nœud tenant en face de bits. Cela va faire ce bit particulier1
de maximiser xor valeur. Si il n'y a pas de nœud à l'opposé bits, alors seulement traverser les mêmes bits de nœud.arr[i]
en trie.Pour
N
éléments, nous avons besoin d'une requête(O(logN)
) et un point d'insertion(O(logN)
) pour chaque élément. Donc, l'ensemble de la durée de la complexité estO(NlogN)
.Vous pouvez trouver bon picturale explication sur la façon dont il fonctionne dans ce fil.
Ici est le C++, la mise en œuvre de l'algorithme ci-dessus:
Une très intéressante problème!
Voici mon idée:
de représentation et de les trier dans l'arbre bit de poids fort en premier
(ajouter des zéros non significatifs pour le match le plus long nombre). Lorsque terminé, chaque chemin
à partir de la racine de toute la feuille représente un nombre à partir de l'original
ensemble.
Si a et b atteignent une feuille, le doit pointer vers deux numéros avec "très peu" à l'identique bits.
Je viens de faire cet algorithme et de ne pas savoir s'il est correct ou la façon de le prouver. Cependant, il devrait être en O(n) temps de fonctionnement.
Faire une fonction récursive qui prend deux listes d'entiers A et B, comme ses arguments. Comme sa valeur de retour, il retourne deux entiers, l'un de A et de B, qui maximisent le XOR de deux. Si tous les entiers de 0, de retour de (0,0). Sinon, la fonction fait un peu de traitement et appelle récursivement deux fois, mais avec de plus petits nombres entiers. Dans l'un des appels récursifs, il considère que la prise d'un nombre entier à partir d'Une liste pour la fourniture de 1 à k bits, et dans l'autre appel il envisage de prendre un nombre entier à partir de la liste B pour la fourniture de 1 à k bits.
Je n'ai pas le temps maintenant de remplir les détails, mais peut-être que ce sera assez pour voir la réponse? Aussi, je ne suis pas sûr si le temps d'exécution sera meilleure que les N^2, mais il sera probablement.
Nous pouvons trouver le nombre maximum en O(n) le temps ensuite une boucle à travers la matrice de faire xor avec chaque élément. En supposant opération xor coût est O(1), nous pouvons trouver max xor de deux nombres en O(n) fois.