Deux éléments dans un tableau dont le xor est maximum

Ignorer le bit de signe, l'une des valeurs doit être l'une des valeurs les plus importantes ensemble de bits. sauf si toutes les valeurs ont ce bit défini , auquel cas vous passez au bit significatif le plus élevé qui n'est pas défini dans toutes les valeurs. Ainsi, vous pouvez réduire les possibilités pour la valeur 1st en regardant le HSB. Par exemple, si les possibilités sont

0x100000
0x100ABC
0x001ABC
0x000ABC

La 1ère valeur de la paire max doit être 0x100000 ou 0x10ABCD.

@ Erreur interne du serveur I ne pensez pas que le plus petit est nécessairement correct. Je n'ai pas une bonne idée pour éplucher la 2ème valeur. Juste n'importe quelle valeur qui n'est pas dans la liste des 1ère valeurs possibles. Dans mon exemple, 0x001ABC ou 0x000ABC.

Cela peut être résolu dans O(NlogN) complexité temporelle en utilisant Trie .

• construire un trie. Pour chaque clé entière, chaque nœud du trie contiendra chaque bit (0 ou 1) à partir du bit le plus significatif.
• maintenant pour chaque élément {[2] } de arr[0, 1, ..... N]
  • effectuez une requête pour récupérer la valeur xor maximale possible pour arr[i]. Nous savons xor de différents types de bits(0 ^ 1 ou 1 ^ 0) est toujours 1. Donc, pendant la requête pour chaque bit, essayez de traverser le nœud contenant le bit opposé. Cela rendra ce bit particulier 1 résultat en maximisant la valeur xor. S'il n'y a pas de nœud avec bit opposé, alors seulement traverser le même nœud de bit.
  • après la requête, insérez arr[i] dans trie.
  • pour chaque élément, Gardez une trace de la valeur Xor maximale possible.
  • en parcourant chaque nœud, construisez l'autre clé pour laquelle le Xor est maximisé.

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, la complexité globale du temps est O(NlogN).

Vous pouvez trouver une belle explication picturale sur la façon dont cela fonctionne dans ce fil .

Voici l'implémentation C++ de l'algorithme ci-dessus:

const static int SIZE = 2;
const static int MSB = 30;
class trie {
private:
    struct trieNode {
        trieNode* children[SIZE];
        trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                children[i] = nullptr;
            }
        }
        ~trieNode() {
            for(int i = 0; i < SIZE; ++i) {
                delete children[i];
                children[i] = nullptr;
            }
        }
    };
    trieNode* root;
public:
    trie(): root(new trieNode()) {
    }
    ~trie() {
        delete root;
        root = nullptr;
    }

    void insert(int key) {
        trieNode* pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(!pCrawl->children[bit]) {
                pCrawl->children[bit] = new trieNode();
            }
            pCrawl = pCrawl->children[bit];
        }
    }

    int query(int key, int& otherKey) {
        int Xor = 0;
        trieNode *pCrawl = root;
        for(int i = MSB; i >= 0; --i) {
            bool bit = (bool)(key & (1 << i));
            if(pCrawl->children[!bit]) {
                pCrawl = pCrawl->children[!bit];
                Xor |= (1 << i);
                if(!bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
            } else {
                if(bit) {
                    otherKey |= (1 << i); 
                } else {
                    otherKey &= ~(1 << i);
                }
                pCrawl = pCrawl->children[bit];
            }
        }
        return Xor;
    }
};

pair<int, int> findMaximumXorElements(vector<int>& arr) {
    int n = arr.size();
    int maxXor = 0;
    pair<int, int> result; 
    if(n < 2) return result;
    trie* Trie = new trie();
    Trie->insert(0); // insert 0 initially otherwise first query won't find node to traverse
    for(int i = 0; i < n; i++) {
        int elem = 0;
        int curr = Trie->query(arr[i], elem);
        if(curr > maxXor) {
            maxXor = curr;
            result = {arr[i], elem};
        }
        Trie->insert(arr[i]);
    }
    delete Trie;
    return result;
}

Un problème très intéressant! Voici mon idée:

• construisez D'abord un arbre binaire à partir de tous les nombres en utilisant le binaire représentation et les trier dans l'arbre bit le plus significatif en premier (ajoutez des zéros en tête pour correspondre au nombre le plus long). Lorsque vous avez terminé chaque chemin de la racine à n'importe quelle feuille représente un nombre de l'original définir.
• Laissez a et b être des pointeurs vers un nœud d'arbre et initialisez-les à la racine.
• Déplacez maintenant a et b dans l'arbre, en essayant d'utiliser des bords opposés a chaque étape, c'est-à-dire si a descend un bord 0, b descend un bord 1 sauf si ce n'est pas possible.

Si a et b atteignent une feuille, le devrait pointer vers deux nombres avec "très peu" de bits identiques.

Je viens de faire cet algorithme et je ne sais pas si c'est correct ou comment le prouver. Cependant, il devrait être en O (N) temps d'exécution.

Crée une fonction récursive qui prend deux listes d'entiers, A et B, comme arguments. Comme valeur de retour, il renvoie deux entiers, un de A et un de B, qui maximisent le XOR des deux. Si tous les entiers sont 0, return (0,0). Sinon, la fonction effectue un traitement et s'appelle récursivement deux fois, mais avec des entiers plus petits. Dans l'un des appels récursifs, il considère prendre un entier de la liste A pour fournir un 1 au bit k, et dans l'autre appel, il considère prendre un entier de la liste B pour fournir un 1 au bit K.

Je n'ai pas le temps maintenant de remplir les détails, mais peut-être que ce sera assez pour voir la réponse? En outre, Je ne suis pas sûr si le temps d'exécution sera meilleur que N^2, mais ce sera probablement le cas.

Nous pouvons trouver le nombre maximum dans le temps O(N) puis parcourir le tableau en faisant xor avec chaque élément. En supposant que le coût d'opération xor est O (1), Nous pouvons trouver max xor de deux nombres dans le temps O(n).