python - 查询的最小异或

标签 python algorithm sorting bit-manipulation xor

我在面试中被问到以下问题。

给定一个包含 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]

因为当 4 与任意元素进行异或运算时 A[I] = 6 时会出现最小值

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 中的每个元素进行排序。我会尝试使用二分搜索找到它在数组 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]

这是 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

最佳答案

关键概念是通过匹配尽可能多的最高有效位来最小化异或。例如,考虑 B[x] = 4,当 A 中的值为

1  0001
2  0010
3  0011
6  0110
9  1001

4 的二进制模式是 0100。所以我们要寻找一个以 0 开头的数字。这消除了 9,因为 9 的最高有效位是 1。接下来,我们在第二位中寻找 1。只有 6 以 01 开头,因此 6 是 4 的最佳匹配。

为了有效地解决问题,我将 A 的元素放入 trie 中。 。

使用问题中的示例,特里树看起来像这样。 (请注意,通过允许特里树中的叶节点位于较高位置,可以节省内存并提高速度,但这会使特里树的构造变得复杂。)

enter image description here

一旦构建了树,就可以轻松查找任何 B[x] 的答案。只需遵循从根开始的位模式即可。对于有两个子节点的节点,转到与当前位匹配的子节点。对于只有一个子节点的节点,别无选择,因此转到该子节点。当找到一片叶子时,这就是答案。

运行时间为 O(k(N+M)),其中 kA 中最大数字的位数。
在示例中,k 为 4。

关于python - 查询的最小异或,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59165778/

相关文章:

python - 奇怪的 PYTHONPATH 问题

python - 使用 Python 进行准随机化

algorithm - 获取链表中倒数第 n 个元素

java - 在java面试中写一个co relation

c++ - 使用数组对整数进行排序。

python - urllib2 - 能够跳过证书验证

python - 如何在按下按钮时更改 Tkinter 标签文本

java - 为什么这个值的输出结果总是零?

python - 使用 lambda 对字典的元素进行排序

java - 需要对字符串值进行排序,同时忽略对空字符串值的任何位置更改