421. 數(shù)組中兩個數(shù)的最大異或值

Idea

假設(shè)選擇了數(shù)組中的元素a_i和a_j使得它們達(dá)到最大按位異或結(jié)果x:$x=a_i\oplus a_j$，其中⊕表示按位異或運(yùn)算。

根據(jù)異或運(yùn)算的性質(zhì)，$x=a_i\oplus a_j$等價于$a_j=a_i\oplus x$，根據(jù)這一變換，可以設(shè)計一種[從高位到低位依次確定x二進(jìn)制表示的每一位]的方法，以此得到x的值。

數(shù)組中的元素都在[0, 2³¹)的范圍內(nèi)，可以將每一個數(shù)都表示為一個長度為31位的二進(jìn)制數(shù)（不滿31位補(bǔ)前導(dǎo)0）字符串，然后可以從最高位第30個二進(jìn)制位開始依次確定x的每一位是0還是1。

由于需要找出最大的x，因此在枚舉每一位時，需要先判斷x的這一位是否能取到1，如果能，就取這一位為1，否則取這一位為0。

將字符串放入字典樹中，那么在字符串中查詢一個字符串的過程，就是從高位開始確定每一個二進(jìn)制位的過程。

$x=a_i\oplus a_j$，枚舉a_i，將a₀, a₁, …, a_i-1作為a_j放入字典樹，希望找到使得x達(dá)到最大值的a_j。

從字典樹的根節(jié)點(diǎn)開始進(jìn)行遍歷，遍歷的[參照對象]為a_i，根據(jù)a_i的第x個二進(jìn)制位時0還是1確定應(yīng)該走哪個子節(jié)點(diǎn)。

假設(shè)當(dāng)前遍歷到第k個二進(jìn)制位：

• 如果a_i的第k個二進(jìn)制位為0，那么應(yīng)該往表示1的子節(jié)點(diǎn)走。如果不存在表示1的子節(jié)點(diǎn)，就只能往表示0的子節(jié)點(diǎn)走。
• 如果a_i的第k個二進(jìn)制位為1，那么應(yīng)該往表示0的子節(jié)點(diǎn)走。如果不存在表示0的子節(jié)點(diǎn)，就只能往表示1的子節(jié)點(diǎn)走。

遍歷完所有的31個二進(jìn)制位后，得到a_i可以通過異或運(yùn)算得到的最大x。

Code

Python

from typing import Listclass Trie:def __init__(self):self.left, self.right = None, Noneclass Solution:def findMaximumXOR(self, nums: List[int]) -> int:root = Trie()HIGH_BIT = 30def add(num: int) -> None:cur = rootfor k in range(HIGH_BIT, -1, -1):bit = (num >> k) & 1if bit == 0:if not cur.left:cur.left = Trie()cur = cur.leftelse:if not cur.right:cur.right = Trie()cur = cur.rightdef check(num: int) -> int:cur = rootx = 0for k in range(HIGH_BIT, -1, -1):bit = (num >> k) & 1if bit == 0:if cur.right:cur = cur.rightx = x * 2 + 1else:cur = cur.leftx = x * 2else:if cur.left:cur = cur.leftx = x * 2 + 1else:cur = cur.rightx = x * 2return xn, x = len(nums), 0for i in range(1, n):add(nums[i - 1])x = max(x, check(nums[i]))return x

總結(jié)

以上是生活随笔為你收集整理的LeetCode 421. 数组中两个数的最大异或值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。