如何實(shí)現(xiàn)數(shù)組中兩個(gè)數(shù)的最大異或值

本篇內(nèi)容介紹了“如何實(shí)現(xiàn)數(shù)組中兩個(gè)數(shù)的最大異或值”的有關(guān)知識，在實(shí)際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

數(shù)組中兩個(gè)數(shù)的最大異或值

給你一個(gè)整數(shù)數(shù)組 nums ，返回 nums[i] XOR nums[j] 的最大運(yùn)算結(jié)果，其中 0 ≤ i ≤ j < n 。

進(jìn)階：你可以在 O(n) 的時(shí)間解決這個(gè)問題嗎？

提示：

• 1 <= nums.length <= 2 * 104

• 0 <= nums[i] <= 231 - 1

鏈接：https://leetcode-cn.com/problems/maximum-xor-of-two-numbers-in-an-array

示例 1：

輸入：nums = [3,10,5,25,2,8]
輸出：28
解釋：最大運(yùn)算結(jié)果是 5 XOR 25 = 28.

示例 2：

輸入：nums = [0]
輸出：0

• XOR : 異或運(yùn)算，1^1=0, 0^0=0, 1^0=1, 0^1=1

// 普通 : O(n^2)   雙重循環(huán)，解決
class Solution {
    public int findMaximumXOR(int[] nums) {
        if(nums == null || nums.length <=1){
            return 0;
        }
        int len = nums.length;
        int res = 0;
        int n = 0;
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if((n=nums[i] ^ nums[j]) > res){
                    res = n; 
                }
            }
        }
        return res;
    }
}

// 進(jìn)階 ：O(n) : 字典樹+貪心
class Tire{     // 樹節(jié)點(diǎn)，左節(jié)點(diǎn)為0，右節(jié)點(diǎn)為1
	Tire left = null; // 0
	Tire right = null; // 1
}

class Solution {
    static Tire root = new Tire(); 
	static final int TIRE_HIGHT = 30; // 樹的深度，2^31 - 1，個(gè)人認(rèn)為是31，當(dāng)30就能滿足條件

    public int findMaximumXOR(int[] nums) {
        root = new Tire();  // Leetcode中全局變量的問題，需要自己初始化
        if(nums == null || nums.length <=1){
            return 0;
        }
        int len = nums.length;
        int res = 0;
        for(int num:nums) {
			add(num);
			res = Math.max(res, check(num));		
		}	
        return res;
    }
	// 生成樹，關(guān)鍵：bit =（num>>i）&1,從高位開始構(gòu)建樹，高位越高，ROX才越大。
	public static void add(int num) {
		Tire node = root;
		for (int i = TIRE_HIGHT; i >= 0; i--) {
			int bit = (num >> i)&1;
			if (bit == 0) {
				  if(node.left == null) {
					  node.left = new Tire();
				  }
				  node = node.left;
			}else {
				if (node.right == null) {
					node.right = new Tire();
				}
				node = node.right;
			}
		}
	}
		// 貪心算法計(jì)算ROX，num某位是1，則找0；反之，找1. 
    	public static int check(int num) {
		Tire node = root;
		int x = 0;
		for (int i = TIRE_HIGHT; i >= 0; i--) {
			int bit = (num >> i)&1;
			if (bit==0) {
				if (node.right != null) { 
					node = node.right;
					x = (x << 1) + 1; 
				}else {
					node = node.left;
					x = (x << 1);
				}
			}else {
				if(node.left != null) {
					node = node.left;
					x = (x << 1) + 1;
				}else {
					node = node.right;
					x = (x << 1);
				}
			}
		}
		return x;
	}

}

總結(jié)：在數(shù)組中找異或值，通過0，1構(gòu)建樹。最大異或值：從高位開始找，通過貪心的思想該位置的異或值等于1最優(yōu)。

“如何實(shí)現(xiàn)數(shù)組中兩個(gè)數(shù)的最大異或值”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！