rust 解法, 执行用时: 20 ms, 内存消耗: 4.9 MB, 提交时间: 2023-11-04 10:22:24

use std::collections::HashSet;

impl Solution {
    pub fn find_maximum_xor(nums: Vec<i32>) -> i32 {
        let mx = *nums.iter().max().unwrap();
        let high_bit = 31 - mx.leading_zeros() as i32;

        let mut ans = 0;
        let mut mask = 0;
        let mut seen = HashSet::new();
        for i in (0..=high_bit).rev() { // 从最高位开始枚举
            seen.clear();
            mask |= 1 << i;
            let new_ans = ans | (1 << i); // 这个比特位可以是 1 吗？
            for &x in &nums {
                let x = x & mask; // 低于 i 的比特位置为 0
                if seen.contains(&(new_ans ^ x)) {
                    ans = new_ans; // 这个比特位可以是 1
                    break;
                }
                seen.insert(x);
            }
        }
        ans
    }
}

golang 解法, 执行用时: 92 ms, 内存消耗: 11.9 MB, 提交时间: 2023-11-04 10:22:06

func findMaximumXOR(nums []int) (ans int) {
    highBit := bits.Len(uint(slices.Max(nums))) - 1
    seen := map[int]bool{}
    mask := 0
    for i := highBit; i >= 0; i-- { // 从最高位开始枚举
        clear(seen)
        mask |= 1 << i
        newAns := ans | 1<<i // 这个比特位可以是 1 吗？
        for _, x := range nums {
            x &= mask // 低于 i 的比特位置为 0
            if seen[newAns^x] {
                ans = newAns // 这个比特位可以是 1
                break
            }
            seen[x] = true
        }
    }
    return
}

javascript 解法, 执行用时: 84 ms, 内存消耗: 60.2 MB, 提交时间: 2023-11-04 10:21:51

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMaximumXOR = function (nums) {
    const highBit = 31 - Math.clz32(Math.max(...nums));
    const seen = new Set();
    let ans = 0, mask = 0;
    for (let i = highBit; i >= 0; i--) { // 从最高位开始枚举
        seen.clear();
        mask |= 1 << i;
        const newAns = ans | (1 << i); // 这个比特位可以是 1 吗？
        for (let x of nums) {
            x &= mask; // 低于 i 的比特位置为 0
            if (seen.has(newAns ^ x)) {
                ans = newAns; // 这个比特位可以是 1
                break;
            }
            seen.add(x);
        }
    }
    return ans;
};

cpp 解法, 执行用时: 168 ms, 内存消耗: 71.9 MB, 提交时间: 2023-11-04 10:21:33

class Solution {
public:
    int findMaximumXOR(vector<int> &nums) {
        int mx = *max_element(nums.begin(), nums.end());
        int high_bit = mx ? 31 - __builtin_clz(mx) : -1;

        int ans = 0, mask = 0;
        unordered_set<int> seen;
        for (int i = high_bit; i >= 0; i--) { // 从最高位开始枚举
            seen.clear();
            mask |= 1 << i;
            int new_ans = ans | (1 << i); // 这个比特位可以是 1 吗？
            for (int x : nums) {
                x &= mask; // 低于 i 的比特位置为 0
                if (seen.contains(new_ans ^ x)) {
                    ans = new_ans; // 这个比特位可以是 1
                    break;
                }
                seen.insert(x);
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 20 ms, 内存消耗: 74.7 MB, 提交时间: 2023-11-04 10:21:19

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int x : nums) {
            max = Math.max(max, x);
        }
        int highBit = 31 - Integer.numberOfLeadingZeros(max);

        int ans = 0, mask = 0;
        Set<Integer> seen = new HashSet<>();
        for (int i = highBit; i >= 0; i--) { // 从最高位开始枚举
            seen.clear();
            mask |= 1 << i;
            int newAns = ans | (1 << i); // 这个比特位可以是 1 吗？
            for (int x : nums) {
                x &= mask; // 低于 i 的比特位置为 0
                if (seen.contains(newAns ^ x)) {
                    ans = newAns; // 这个比特位可以是 1
                    break;
                }
                seen.add(x);
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 88 ms, 内存消耗: 40.7 MB, 提交时间: 2023-11-04 10:21:05

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = mask = 0
        high_bit = max(nums).bit_length() - 1
        for i in range(high_bit, -1, -1):  # 从最高位开始枚举
            mask |= 1 << i
            new_ans = ans | (1 << i)  # 这个比特位可以是 1 吗？
            seen = set()
            for x in nums:
                x &= mask  # 低于 i 的比特位置为 0
                if new_ans ^ x in seen:
                    ans = new_ans  # 这个比特位可以是 1
                    break
                seen.add(x)
        return ans

python3 解法, 执行用时: 1476 ms, 内存消耗: 55.6 MB, 提交时间: 2023-08-22 15:24:00

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        highBit = 30 # 最高位的二进制位编号为 30
        x = 0
        for k in range(highBit, -1, -1):
            # 将所有的 pre^k(a_j) 放入哈希表中
            seen = defaultdict(bool)
            for num in nums:
                # 如果只想保留从最高位开始到第 k 个二进制位为止的部分
                # 只需将其右移 k 位
                seen[num>>k] = True
    
            # 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
            # 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
            xNext = x*2 + 1
            found = False
    
            # 枚举 i
            for num in nums:
                if seen[num>>k^xNext]:
                    found = True
                    break
    
            if found:
                x = xNext
            else:
                # 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
                # 即为 x = x*2
                x = xNext - 1
        return x

golang 解法, 执行用时: 236 ms, 内存消耗: 10.2 MB, 提交时间: 2022-11-20 17:41:19

func findMaximumXOR(nums []int) (x int) {
    const highBit = 30 // 最高位的二进制位编号为 30
    for k := highBit; k >= 0; k-- {
        // 将所有的 pre^k(a_j) 放入哈希表中
        seen := map[int]bool{}
        for _, num := range nums {
            // 如果只想保留从最高位开始到第 k 个二进制位为止的部分
            // 只需将其右移 k 位
            seen[num>>k] = true
        }

        // 目前 x 包含从最高位开始到第 k+1 个二进制位为止的部分
        // 我们将 x 的第 k 个二进制位置为 1，即为 x = x*2+1
        xNext := x*2 + 1
        found := false

        // 枚举 i
        for _, num := range nums {
            if seen[num>>k^xNext] {
                found = true
                break
            }
        }

        if found {
            x = xNext
        } else {
            // 如果没有找到满足等式的 a_i 和 a_j，那么 x 的第 k 个二进制位只能为 0
            // 即为 x = x*2
            x = xNext - 1
        }
    }
    return
}