Question

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

English Version

题目描述

给你一个下标从 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 * 104
• 1 <= nums[i] <= 220 - 1

解法

方法一：排序 + 0-1 字典树

观察不等式 $|x - y| \leq \min(x, y)$，其中涉及到绝对值以及最小值，我们不妨假设 $x \leq y$，则有 $y - x \leq x$，即 $y \leq 2x$。我们可以从小到大枚举 $y$，那么 $x$ 必须满足不等式 $y \leq 2x$。

因此，我们对数组 $nums$ 进行排序，然后从小到大枚举 $y$，利用双指针维护一个窗口，使得窗口内的元素 $x$ 满足不等式 $y \leq 2x$。我们可以使用 0-1 字典树来维护窗口内的元素，这样我们就可以在 $O(1)$ 的时间内找到窗口内的最大异或值。每一次我们将 $y$ 加入到字典树中，同时将窗口左端点不满足不等式的元素移除，这样就可以保证窗口内的元素满足不等式 $y \leq 2x$。然后从字典树中查询最大异或值，更新答案。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(n \times \log M)$。其中 $n$ 是数组 $nums$ 的长度，而 $M$ 是数组 $nums$ 中的最大值，本题中 $M = 2^{20}$。

class Trie:
  __slots__ = ("children", "cnt")

  def __init__(self):
    self.children: List[Trie | None] = [None, None]
    self.cnt = 0

  def insert(self, x: int):
    node = self
    for i in range(20, -1, -1):
      v = x >> i & 1
      if node.children[v] is None:
        node.children[v] = Trie()
      node = node.children[v]
      node.cnt += 1

  def search(self, x: int) -> int:
    node = self
    ans = 0
    for i in range(20, -1, -1):
      v = x >> i & 1
      if node.children[v ^ 1] and node.children[v ^ 1].cnt:
        ans |= 1 << i
        node = node.children[v ^ 1]
      else:
        node = node.children[v]
    return ans

  def remove(self, x: int):
    node = self
    for i in range(20, -1, -1):
      v = x >> i & 1
      node = node.children[v]
      node.cnt -= 1


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

class Trie {
  private Trie[] children = new Trie[2];
  private int cnt = 0;

  public Trie() {
  }

  public void insert(int x) {
    Trie node = this;
    for (int i = 20; i >= 0; --i) {
      int v = x >> i & 1;
      if (node.children[v] == null) {
        node.children[v] = new Trie();
      }
      node = node.children[v];
      ++node.cnt;
    }
  }

  public int search(int x) {
    Trie node = this;
    int ans = 0;
    for (int i = 20; i >= 0; --i) {
      int v = x >> i & 1;
      if (node.children[v ^ 1] != null && node.children[v ^ 1].cnt > 0) {
        ans |= 1 << i;
        node = node.children[v ^ 1];
      } else {
        node = node.children[v];
      }
    }
    return ans;
  }

  public void remove(int x) {
    Trie node = this;
    for (int i = 20; i >= 0; --i) {
      int v = x >> i & 1;
      node = node.children[v];
      --node.cnt;
    }
  }
}

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

class Trie {
public:
  Trie* children[2];
  int cnt;

  Trie()
    : cnt(0) {
    children[0] = nullptr;
    children[1] = nullptr;
  }

  void insert(int x) {
    Trie* node = this;
    for (int i = 20; ~i; --i) {
      int v = (x >> i) & 1;
      if (node->children[v] == nullptr) {
        node->children[v] = new Trie();
      }
      node = node->children[v];
      ++node->cnt;
    }
  }

  int search(int x) {
    Trie* node = this;
    int ans = 0;
    for (int i = 20; ~i; --i) {
      int v = (x >> i) & 1;
      if (node->children[v ^ 1] != nullptr && node->children[v ^ 1]->cnt > 0) {
        ans |= 1 << i;
        node = node->children[v ^ 1];
      } else {
        node = node->children[v];
      }
    }
    return ans;
  }

  void remove(int x) {
    Trie* node = this;
    for (int i = 20; ~i; --i) {
      int v = (x >> i) & 1;
      node = node->children[v];
      --node->cnt;
    }
  }
};

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

type Trie struct {
  children [2]*Trie
  cnt    int
}

func newTrie() *Trie {
  return &Trie{}
}

func (t *Trie) insert(x int) {
  node := t
  for i := 20; i >= 0; i-- {
    v := (x >> uint(i)) & 1
    if node.children[v] == nil {
      node.children[v] = newTrie()
    }
    node = node.children[v]
    node.cnt++
  }
}

func (t *Trie) search(x int) int {
  node := t
  ans := 0
  for i := 20; i >= 0; i-- {
    v := (x >> uint(i)) & 1
    if node.children[v^1] != nil && node.children[v^1].cnt > 0 {
      ans |= 1 << uint(i)
      node = node.children[v^1]
    } else {
      node = node.children[v]
    }
  }
  return ans
}

func (t *Trie) remove(x int) {
  node := t
  for i := 20; i >= 0; i-- {
    v := (x >> uint(i)) & 1
    node = node.children[v]
    node.cnt--
  }
}

func maximumStrongPairXor(nums []int) (ans int) {
  sort.Ints(nums)
  tree := newTrie()
  i := 0
  for _, y := range nums {
    tree.insert(y)
    for ; y > nums[i]*2; i++ {
      tree.remove(nums[i])
    }
    ans = max(ans, tree.search(y))
  }
  return ans
}

class Trie {
  children: (Trie | null)[];
  cnt: number;

  constructor() {
    this.children = [null, null];
    this.cnt = 0;
  }

  insert(x: number): void {
    let node: Trie | null = this;
    for (let i = 20; i >= 0; i--) {
      const v = (x >> i) & 1;
      if (node.children[v] === null) {
        node.children[v] = new Trie();
      }
      node = node.children[v] as Trie;
      node.cnt++;
    }
  }

  search(x: number): number {
    let node: Trie | null = this;
    let ans = 0;
    for (let i = 20; i >= 0; i--) {
      const v = (x >> i) & 1;
      if (node.children[v ^ 1] !== null && (node.children[v ^ 1] as Trie).cnt > 0) {
        ans |= 1 << i;
        node = node.children[v ^ 1] as Trie;
      } else {
        node = node.children[v] as Trie;
      }
    }
    return ans;
  }

  remove(x: number): void {
    let node: Trie | null = this;
    for (let i = 20; i >= 0; i--) {
      const v = (x >> i) & 1;
      node = node.children[v] as Trie;
      node.cnt--;
    }
  }
}

function maximumStrongPairXor(nums: number[]): number {
  nums.sort((a, b) => a - b);
  const tree = new Trie();
  let ans = 0;
  let i = 0;

  for (const y of nums) {
    tree.insert(y);

    while (y > nums[i] * 2) {
      tree.remove(nums[i++]);
    }

    ans = Math.max(ans, tree.search(y));
  }

  return ans;
}