查询的最小异或 [英] Minimum XOR for queries
问题描述
我在一次采访中被问到以下问题.
给定一个包含 N 个元素的数组 A 和一个包含 M 个元素的数组 B.对于每个 B[X] 返回 A[I]，其中 A[I] 和 B[X] 的 XOR 最小.
例如:
输入
A = [3, 2, 9, 6, 1]B = [4, 8, 5, 9]输出
[6, 9, 6, 9]因为当A[I] = 6时，4与A中的任何元素异或都会出现最小值
4 ^ 3 = 74 ^ 2 = 64 ^ 9 = 134 ^ 6 = 24 ^ 1 = 5这是我在 python 中的蛮力解决方案.
def get_min_xor(A, B):答案 = []对于 B 中的 val_b:min_xor = val_b ^ A[0]对于 A 中的 val_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)返回答案关于如何在子 O(MxN) 时间复杂度中解决这个问题的任何想法?
我有以下想法.我会在 O(NlogN) 时间内对数组 A 进行排序，然后对 B 中的每个元素进行排序.我会尝试使用二进制搜索找到它在数组 A 中的位置.假设 B[X] 将适合 A 中的第 i 个位置，然后我会检查 B[X] ^ A[i-1] 和 B[X] ^ A[i+1] 的最小异或.但这种方法并不适用于所有情况.例如下面的输入
A = [1,2,3]B = [2, 5, 8]输出:
[2, 1, 1]这是特里解决方案.
类树(对象):头 = {}def convert_number(self, number):返回格式(数字，'#032b')def add(self, number):cur_dict = self.headbinary_number = self.convert_number(number)对于 binary_number 中的位:如果位不在 cur_dict 中:cur_dict[位] = {}cur_dict = cur_dict[位]cur_dict[数字] = 真定义搜索(自我，数字):cur_dict = self.headbinary_number = self.convert_number(number)对于 binary_number 中的位:如果位不在 cur_dict 中:如果位==1":cur_dict = cur_dict["0"]别的:cur_dict = cur_dict["1"]别的:cur_dict = cur_dict[位]返回列表(cur_dict.keys())[0]def get_min_xor_with_trie(A,B):number_trie = trie()对于 A 中的 val:number_trie.add(val)答案 = []对于 B 中的 val:ans.append(number_trie.search(val))返回答案关键概念是通过匹配尽可能多的最高有效位来最小化 XOR.例如，考虑 B[x] = 4，当 A 中的值是
1 00012 00103 00116 01109 10014 的二进制模式是 0100.所以我们正在寻找一个以 0 开头的数字.这消除了 9，因为 9 有一个 1 作为最高有效位.接下来，我们在第二位中寻找 1.只有 6 个以 01 开头，所以 6 是 4 的最佳匹配.
为了有效地解决问题，我会将 A 的元素放入
一旦构建了树，就很容易查找任何 B[x] 的答案.只需遵循从根开始的位模式即可.对于有两个子节点的节点，转到与当前位匹配的子节点.对于只有一个孩子的节点，别无选择，所以去那个孩子.当找到一片叶子时，这就是答案.
运行时间为 O(k(N+M))，其中 k 是 A 中最大数的位数.
在示例中，k 为 4.
I was asked the following question in an interview.
Given an array A with N elements and an array B with M elements. For each B[X] return A[I] where XOR of A[I] and B[X] is minimum.
For example:
Input
A = [3, 2, 9, 6, 1]
B = [4, 8, 5, 9]
Output
[6, 9, 6, 9]
Because when 4 is XORed with any element in A minimum value will occur when A[I] = 6
4 ^ 3 = 7
4 ^ 2 = 6
4 ^ 9 = 13
4 ^ 6 = 2
4 ^ 1 = 5
Here is my brute force solution in 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
Any ideas on how this could be solved in sub O(MxN) time complexity?
I had the following idea in mind.
I would sort the array A in O(NlogN) time then for each element in B. I would try to find it's place in the array A using binary search.Let's say B[X] would fit at ith position in A then I would check the min XOR of B[X] ^ A[i-1] and B[X] ^ A[i+1]. But this approach won't work in all the cases. For example the following input
A = [1,2,3]
B = [2, 5, 8]
Output:
[2, 1, 1]
Here is the trie solution.
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
The key concept is that the XOR is minimized by matching as many of the most-significant bits as possible. For example, consider B[x] = 4, when the values in A are
1 0001
2 0010
3 0011
6 0110
9 1001
The binary pattern for 4 is 0100. So we're looking for a number that starts with 0. This eliminates the 9, since 9 has a 1 as the most-significant bit. Next, we're looking for a 1 in the second bit. Only 6 starts with 01, so 6 is the best match for 4.
To solve the problem efficiently, I would put the elements of A into a trie.
Using the example from the question, the trie would look something like this. (Note that it's possible to save memory and improve speed by allowing leaf nodes higher in the trie, but that complicates construction of the trie.)
Once the tree is constructed, it's easy to look up the answer for any B[x]. Just follow the bit pattern starting from the root. For nodes that have two children, go to the child that matches the current bit. For nodes with one child, there's no choice, so go to that child. When a leaf is found, that's the answer.
The run time is O(k(N+M)) where k is the number of bits in the largest number in A.
In the example, k is 4.
这篇关于查询的最小异或的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
