查询的最小 XOR
Minimum XOR for queries
我在面试中被问到以下问题。
给定一个包含 N 个元素的数组 A 和一个包含 [=41] 个元素的数组 B =]M个元素。对于每个 B[X] return A[I],其中 A[I] 和 B[X] 的异或最小值。
例如:
输入
A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]
输出
[6, 9, 6, 9]
因为当A[I] = 6
时,4与中的任何元素异或都会出现最小值
4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5
这是我在 python 中的暴力解决方案。
def get_min_xor(A, B):
ans = []
for val_b in B:
min_xor = val_b ^ A[0]
for val_a in A:
min_xor = min(min_xor, val_b ^ val_a)
# print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))
ans.append(min_xor ^ val_b)
return ans
关于如何在子 O(MxN) 时间复杂度内解决这个问题有什么想法吗?
我有以下想法。
我会在 O(NlogN) 时间内对数组 A 进行排序,然后对 B 中的每个元素进行排序。我会尝试使用二进制 search.Let 找到它在数组 A 中的位置,比如 B[X] 适合然后我会检查 B[X] ^ A[i-1]
和 B[X] ^ A[i+1]
的最小 XOR。但这种方法并非在所有情况下都有效。比如下面的输入
A = [1,2,3]
B = [2, 5, 8]
输出:
[2, 1, 1]
这是 trie 解决方案。
class trie(object):
head = {}
def convert_number(self, number):
return format(number, '#032b')
def add(self, number):
cur_dict = self.head
binary_number = self.convert_number(number)
for bit in binary_number:
if bit not in cur_dict:
cur_dict[bit] = {}
cur_dict = cur_dict[bit]
cur_dict[number] = True
def search(self, number):
cur_dict = self.head
binary_number = self.convert_number(number)
for bit in binary_number:
if bit not in cur_dict:
if bit == "1":
cur_dict = cur_dict["0"]
else:
cur_dict = cur_dict["1"]
else:
cur_dict = cur_dict[bit]
return list(cur_dict.keys())[0]
def get_min_xor_with_trie(A,B):
number_trie = trie()
for val in A:
number_trie.add(val)
ans = []
for val in B:
ans.append(number_trie.search(val))
return ans
关键概念是通过匹配尽可能多的 most-significant 位来最小化 XOR。例如,考虑 B[x] = 4,当 A 中的值是
1 0001
2 0010
3 0011
6 0110
9 1001
4 的二进制模式是 0100
。所以我们正在寻找一个以 0 开头的数字。这消除了 9,因为 9 有一个 1 作为 most-significant 位。接下来,我们要寻找第二位中的 1。只有 6 以 01
开头,所以 6 是 4.
的最佳匹配
为了有效地解决问题,我会将 A 的元素放入 trie。
使用问题中的示例,trie 看起来像这样。 (请注意,通过在 trie 中允许更高的叶节点可以节省内存并提高速度,但这会使 trie 的构造复杂化。)
构建树后,很容易查找任何 B[x] 的答案。只需遵循从根开始的位模式。对于有两个children的节点,转到与当前位匹配的child。对于有一个 child 的节点,没有选择,所以转到那个 child。当找到一片叶子时,这就是答案。
运行时间为O(k(N+M)) 其中k
是A中最大数的位数。
在示例中,k
为 4。
我在面试中被问到以下问题。
给定一个包含 N 个元素的数组 A 和一个包含 [=41] 个元素的数组 B =]M个元素。对于每个 B[X] return A[I],其中 A[I] 和 B[X] 的异或最小值。
例如:
输入
A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]
输出
[6, 9, 6, 9]
因为当A[I] = 6
时,4与中的任何元素异或都会出现最小值4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5
这是我在 python 中的暴力解决方案。
def get_min_xor(A, B):
ans = []
for val_b in B:
min_xor = val_b ^ A[0]
for val_a in A:
min_xor = min(min_xor, val_b ^ val_a)
# print("{} ^ {} = {}".format(val_b, val_a, val_b ^ val_a))
ans.append(min_xor ^ val_b)
return ans
关于如何在子 O(MxN) 时间复杂度内解决这个问题有什么想法吗?
我有以下想法。
我会在 O(NlogN) 时间内对数组 A 进行排序,然后对 B 中的每个元素进行排序。我会尝试使用二进制 search.Let 找到它在数组 A 中的位置,比如 B[X] 适合然后我会检查 B[X] ^ A[i-1]
和 B[X] ^ A[i+1]
的最小 XOR。但这种方法并非在所有情况下都有效。比如下面的输入
A = [1,2,3]
B = [2, 5, 8]
输出:
[2, 1, 1]
这是 trie 解决方案。
class trie(object):
head = {}
def convert_number(self, number):
return format(number, '#032b')
def add(self, number):
cur_dict = self.head
binary_number = self.convert_number(number)
for bit in binary_number:
if bit not in cur_dict:
cur_dict[bit] = {}
cur_dict = cur_dict[bit]
cur_dict[number] = True
def search(self, number):
cur_dict = self.head
binary_number = self.convert_number(number)
for bit in binary_number:
if bit not in cur_dict:
if bit == "1":
cur_dict = cur_dict["0"]
else:
cur_dict = cur_dict["1"]
else:
cur_dict = cur_dict[bit]
return list(cur_dict.keys())[0]
def get_min_xor_with_trie(A,B):
number_trie = trie()
for val in A:
number_trie.add(val)
ans = []
for val in B:
ans.append(number_trie.search(val))
return ans
关键概念是通过匹配尽可能多的 most-significant 位来最小化 XOR。例如,考虑 B[x] = 4,当 A 中的值是
1 0001
2 0010
3 0011
6 0110
9 1001
4 的二进制模式是 0100
。所以我们正在寻找一个以 0 开头的数字。这消除了 9,因为 9 有一个 1 作为 most-significant 位。接下来,我们要寻找第二位中的 1。只有 6 以 01
开头,所以 6 是 4.
为了有效地解决问题,我会将 A 的元素放入 trie。
使用问题中的示例,trie 看起来像这样。 (请注意,通过在 trie 中允许更高的叶节点可以节省内存并提高速度,但这会使 trie 的构造复杂化。)
构建树后,很容易查找任何 B[x] 的答案。只需遵循从根开始的位模式。对于有两个children的节点,转到与当前位匹配的child。对于有一个 child 的节点,没有选择,所以转到那个 child。当找到一片叶子时,这就是答案。
运行时间为O(k(N+M)) 其中k
是A中最大数的位数。
在示例中,k
为 4。