数组中两个数的最大异或值(LeetCode 421)---C++实现

利用字典树，将一个数31位信息存入字典树。然后遍历数组，将每个数取反，在字典树中寻找与取反后的数最匹配的即为数组任一个数与该数异或的最大值。

#include <iostream>
using namespace std;

/*
数组中两数异或最大值
*/

typedef struct Trie {
	struct Trie* datas[2];
	Trie() {
		datas[0] = datas[1] = NULL;
	}
}node;

void insertIntoTrie(node* trie,int num) {
	for (int i = 30; i >= 0; i--) {
		int bit = (num >> i) & 1;
		if (!trie->datas[bit]) {
			trie->datas[bit] = new Trie;
		}
		trie = trie->datas[bit];
	}
}

int findRes(node* trie, int num) {
	if (trie) {
		int res = 0;
		for (int i = 30; i >= 0; i--) {
			int bit = (num >> i) & 1;
			res = res << 1;
			if (trie->datas[bit]) {
				trie = trie->datas[bit];
				res += 1;
			}
			else {
				trie = trie->datas[!bit];
			}
		}
		return res;
	}
}

int main()
{
	Trie *node = new Trie;

	int arr[] = { 3,10,5,25,2,8 };
	insertIntoTrie(node, 3);
	insertIntoTrie(node, 10);
	insertIntoTrie(node, 5);
	insertIntoTrie(node, 25);
	insertIntoTrie(node, 2);
	insertIntoTrie(node, 8);
	int max = -1 << 30;
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++) {
		int t = findRes(node, ~arr[i]);//取反
		max = t > max ? t : max;
	}
	cout << max;

	return 0;
}