位运算数组中两个数的最大异或值贪心算法+树或哈希表

贪心规律&＃xff1a;二进制下&＃xff0c;我们希望一个数尽可能大&＃xff0c;即希望越高位上越能够出现“1”&＃xff0c;这样这个数就是所求的最大数&＃xff0c;这是贪心算法的思想。即我们选择的两个数异或要尽可能让高位为1。

方法一&＃xff1a;建立一个深度为32的树&＃xff0c;从一个数的第31位开始&＃xff0c;如果为0则向左子树走&＃xff0c;否则向右子树走。最后将数放在叶节点中。在查找时&＃xff0c;根据当前的数字&＃xff0c;选择和其搭配使异或值最大的数字。即如果该数的某位为1&＃xff0c;则需要选择另一个数该位为0&＃xff0c;否则只能选1.

int result &＃61; 0;int mask &＃61; 0x0;set num_set;for(int i &＃61; 31; i >&＃61;0; i--){mask &＃61; mask | (0x1 <::iterator it &＃61; num_set.begin(); it !&＃61; num_set.end(); it&＃43;&＃43;){if(num_set.find(*it ^ tem) !&＃61; num_set.end()){ //找到这样的数result &＃61; tem;break;}}num_set.clear(); }return result;


方法二&＃xff1a;用字典的解法&＃xff0c;必须要理解下面的公式&＃xff1a;


我们利用贪心算法思想&＃xff0c;假设我们最大值的尽可能多的高位为1。先假设最大值高位为1&＃xff0c;然后取出vector中数据的高位&＃xff08;即屏蔽低位后放入set中&＃xff09;&＃xff0c;如果有1^0这种组合&＃xff0c;即可说明该位可以为1。然后看结果的次高位是否能为1。屏蔽vector中的数据的除高2位的位数&＃xff0c;加入set中。然后在set中寻找是否有这样的组合使高位和次高位都为1.如果没有&＃xff0c;说明次高位只能是0。寻找组合的过程&＃xff0c;需要用到开头说的公式&＃xff0c;就是当前数异或上待定最大值应该为我们查找的能形成最大值组合的那个数。

struct TreeNode{int val;TreeNode* left;TreeNode* right;TreeNode(int _val): val(_val), left(nullptr), right(nullptr) {}};
public:int findMaximumXOR(vector& nums) {//字典和建树都需要用到贪心算法 //建树 0->left 1->rightTreeNode root(-1); int max &＃61; 0;//先进行建树for(auto num : nums){TreeNode* ptr &＃61; &root;for(int i &＃61; 31; i >&＃61; 0; i--){if(num & (0x1 <right &＃61;&＃61; nullptr){ptr->right &＃61; new TreeNode(1);}ptr &＃61; ptr->right;}else{if(ptr->left &＃61;&＃61; nullptr){ptr->left &＃61; new TreeNode(0);}ptr &＃61; ptr->left;}}ptr->left &＃61; new TreeNode(num);}//应用贪心算法&＃xff0c;查找当前num下能产生最大异或值得组合for(auto num : nums){TreeNode* ptr &＃61; &root;for(int i &＃61; 31; i >&＃61;0; i--){if(num & (0x1 <left){ptr &＃61; ptr->left;}else{ptr &＃61; ptr->right;}}else{if(ptr->right){ptr &＃61; ptr->right;}else{ptr &＃61; ptr->left;}}}if((num^(ptr->left->val)) > max){max &＃61; (num^(ptr->left->val));}}return max;}