找出强数对的最大异或值 II

2935. 找出强数对的最大异或值 II

给你一个下标从 0 开始的整数数组 nums 。如果一对整数 x 和 y 满足以下条件，则称其为 强数对 ：

|x - y| <= min(x, y)

你需要从 nums 中选出两个整数，且满足：这两个整数可以形成一个强数对，并且它们的按位异或（XOR）值是在该数组所有强数对中的 最大值 。

返回数组 nums 所有可能的强数对中的最大异或值。

注意，你可以选择同一个整数两次来形成一个强数对。

示例 1：

输入：nums = [1,2,3,4,5]
输出：7
解释：数组 nums 中有 11 个强数对：(1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (3, 5), (4, 4), (4, 5) 和 (5, 5) 。
这些强数对中的最大异或值是 3 XOR 4 = 7 。

示例 2：

输入：nums = [10,100]
输出：0
解释：数组 nums 中有 2 个强数对：(10, 10) 和 (100, 100) 。
这些强数对中的最大异或值是 10 XOR 10 = 0 ，数对 (100, 100) 的异或值也是 100 XOR 100 = 0 。

示例 3：

输入：nums = [500,520,2500,3000]
输出：1020
解释：数组 nums 中有 6 个强数对：(500, 500), (500, 520), (520, 520), (2500, 2500), (2500, 3000) 和 (3000, 3000) 。
这些强数对中的最大异或值是 500 XOR 520 = 1020 ；另一个异或值非零的数对是 (5, 6) ，其异或值是 2500 XOR 3000 = 636 。

提示：

1 <= nums.length <= 5 * 10⁴
1 <= nums[i] <= 2²⁰ - 1

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int maximumStrongPairXor(vector<int>& nums) { } };

golang 解法, 执行用时: 232 ms, 内存消耗: 21.3 MB, 提交时间: 2023-11-13 20:47:15

const highBit = 19

type node struct {
	children [2]*node
	cnt      int // 子树大小
}

type trie struct{ root *node }

// 添加 val
func (t trie) insert(val int) *node {
	cur := t.root
	for i := highBit; i >= 0; i-- {
		bit := val >> i & 1
		if cur.children[bit] == nil {
			cur.children[bit] = &node{}
		}
		cur = cur.children[bit]
		cur.cnt++ // 维护子树大小
	}
	return cur
}

// 删除 val，但不删除节点
// 要求 val 必须在 t 中
func (t trie) remove(val int) *node {
	cur := t.root
	for i := highBit; i >= 0; i-- {
		cur = cur.children[val>>i&1]
		cur.cnt-- // 维护子树大小
	}
	return cur
}

// 返回 val 与 t 中一个元素的最大异或和
// 要求 t 不能为空
func (t trie) maxXor(val int) (ans int) {
	cur := t.root
	for i := highBit; i >= 0; i-- {
		bit := val >> i & 1
		// 如果 cur.children[bit^1].cnt == 0，视作空节点
		if cur.children[bit^1] != nil && cur.children[bit^1].cnt > 0 {
			ans |= 1 << i
			bit ^= 1
		}
		cur = cur.children[bit]
	}
	return
}

func maximumStrongPairXor(nums []int) (ans int) {
	slices.Sort(nums)
	t := trie{&node{}}
	left := 0
	for _, y := range nums {
		t.insert(y)
		for nums[left]*2 < y {
			t.remove(nums[left])
			left++
		}
		ans = max(ans, t.maxXor(y))
	}
	return
}

java 解法, 执行用时: 104 ms, 内存消耗: 73.1 MB, 提交时间: 2023-11-13 20:47:01

class Node {
    Node[] children = new Node[2];
    int cnt; // 子树大小
}

class Trie {
    private static final int HIGH_BIT = 19;
    private Node root = new Node();

    // 添加 val
    public void insert(int val) {
        Node cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (cur.children[bit] == null) {
                cur.children[bit] = new Node();
            }
            cur = cur.children[bit];
            cur.cnt++; // 维护子树大小
        }
    }

    // 删除 val，但不删除节点
    // 要求 val 必须在 trie 中
    public void remove(int val) {
        Node cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            cur = cur.children[(val >> i) & 1];
            cur.cnt--; // 维护子树大小
        }
    }

    // 返回 val 与 trie 中一个元素的最大异或和
    // 要求 trie 不能为空
    public int maxXor(int val) {
        Node cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            // 如果 cur.children[bit^1].cnt == 0，视作空节点
            if (cur.children[bit ^ 1] != null && cur.children[bit ^ 1].cnt > 0) {
                ans |= 1 << i;
                bit ^= 1;
            }
            cur = cur.children[bit];
        }
        return ans;
    }
}

public class Solution {
    public int maximumStrongPairXor(int[] nums) {
        Arrays.sort(nums);
        Trie t = new Trie();
        int ans = 0, left = 0;
        for (int y : nums) {
            t.insert(y);
            while (nums[left] * 2 < y) {
                t.remove(nums[left++]);
            }
            ans = Math.max(ans, t.maxXor(y));
        }
        return ans;
    }
}

cpp 解法, 执行用时: 360 ms, 内存消耗: 141.6 MB, 提交时间: 2023-11-13 20:46:50

class Node {
public:
    array<Node*, 2> children{};
    int cnt = 0; // 子树大小
};

class Trie {
    static const int HIGH_BIT = 19;
public:
    Node *root = new Node();

    // 添加 val
    void insert(int val) {
        Node *cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (cur->children[bit] == nullptr) {
                cur->children[bit] = new Node();
            }
            cur = cur->children[bit];
            cur->cnt++; // 维护子树大小
        }
    }

    // 删除 val，但不删除节点
    // 要求 val 必须在 trie 中
    void remove(int val) {
        Node *cur = root;
        for (int i = HIGH_BIT; i >= 0; i--) {
            cur = cur->children[(val >> i) & 1];
            cur->cnt--; // 维护子树大小
        }
    }

    // 返回 val 与 trie 中一个元素的最大异或和
    // 要求 trie 不能为空
    int max_xor(int val) {
        Node *cur = root;
        int ans = 0;
        for (int i = HIGH_BIT; i >= 0; i--) {
            int bit = (val >> i) & 1;
            // 如果 cur.children[bit^1].cnt == 0，视作空节点
            if (cur->children[bit ^ 1] && cur->children[bit ^ 1]->cnt) {
                ans |= 1 << i;
                bit ^= 1;
            }
            cur = cur->children[bit];
        }
        return ans;
    }
};

class Solution {
public:
    int maximumStrongPairXor(vector<int> &nums) {
        sort(nums.begin(), nums.end());
        Trie t{};
        int ans = 0, left = 0;
        for (int y: nums) {
            t.insert(y);
            while (nums[left] * 2 < y) {
                t.remove(nums[left++]);
            }
            ans = max(ans, t.max_xor(y));
        }
        return ans;
    }
};

python3 解法, 执行用时: 4656 ms, 内存消耗: 53.8 MB, 提交时间: 2023-11-13 20:46:37

class Node:
    __slots__ = 'children', 'cnt'

    def __init__(self):
        self.children = [None, None]
        self.cnt = 0  # 子树大小

class Trie:
    HIGH_BIT = 19

    def __init__(self):
        self.root = Node()

    # 添加 val
    def insert(self, val: int) -> None:
        cur = self.root
        for i in range(Trie.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            if cur.children[bit] is None:
                cur.children[bit] = Node()
            cur = cur.children[bit]
            cur.cnt += 1  # 维护子树大小
        return cur

    # 删除 val，但不删除节点
    # 要求 val 必须在 trie 中
    def remove(self, val: int) -> None:
        cur = self.root
        for i in range(Trie.HIGH_BIT, -1, -1):
            cur = cur.children[(val >> i) & 1]
            cur.cnt -= 1  # 维护子树大小
        return cur

    # 返回 val 与 trie 中一个元素的最大异或和
    # 要求 trie 中至少有一个元素
    def max_xor(self, val: int) -> int:
        cur = self.root
        ans = 0
        for i in range(Trie.HIGH_BIT, -1, -1):
            bit = (val >> i) & 1
            # 如果 cur.children[bit^1].cnt == 0，视作空节点
            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:
                ans |= 1 << i
                bit ^= 1
            cur = cur.children[bit]
        return ans

class Solution:
    def maximumStrongPairXor(self, nums: List[int]) -> int:
        nums.sort()
        t = Trie()
        ans = left = 0
        for y in nums:
            t.insert(y)
            while nums[left] * 2 < y:
                t.remove(nums[left])
                left += 1
            ans = max(ans, t.max_xor(y))
        return ans

上一题

下一题

详情