我在最近的一次采访中遇到了这个问题:
给定A
长度数组N
,我们应该回答Q
查询。查询形式如下:
给定x
和k
,我们需要制作另一个B
相同长度的数组,使得XOR运算符B[i] = A[i] ^ x
在哪里^
。按降序对数组B
排序并返回B[k]
。
输入格式:第一行包含整数N第二行包含N个表示数组的整数A第三行包含Q,即查询数量接下来的Q行包含以空格分隔的整数x和k
输出格式:在新行中分别打印B [k]值以进行Q查询。
例如用于输入:
5
1 2 3 4 5
2
2 3
0 1
输出将是:
3
5
对于第一个查询,A = [1, 2, 3, 4, 5]
对于查询x = 2
和k = 3
,B = [1^2, 2^2, 3^2, 4^2, 5^2] = [3, 0, 1, 6, 7]
。按降序排序B = [7, 6, 3, 1, 0]
。因此,B[3] = 3
。
对于第二个查询,A
与B
相同x = 0
。所以,B[1] = 5
我不知道如何解决这些问题。提前致谢。
在O(N + Q)中可解决。为简单起见,我假设您只处理正数或无符号值,但是您也可以针对负数调整此算法。
首先,您要建立一个二叉树。左边缘代表0,右边缘代表1。在每个节点中,您存储此存储桶中的数字。这可以在O(N)中完成,因为位数是恒定的。
因为这有点难以解释,所以我将展示3位数字[0、1、4、5、7],即[000、001、100、101、111]的树的外观
*
/ \
2 3 2 numbers have first bit 0 and 3 numbers first bit 1
/ \ / \
2 0 2 1 of the 2 numbers with first bit 0, have 2 numbers 2nd bit 0, ...
/ \ / \ / \
1 1 1 1 0 1 of the 2 numbers with 1st and 2nd bit 0, has 1 number 3rd bit 0, ...
要回答单个查询,您可以使用x位向下浏览。在每个节点上,您有4种可能性,查看x的位b并建立答案a,该答案最初为0:
b = 0且k <存储在当前节点的左子节点(0位分支)中的值:当前节点变为左子节点,a = 2 * a(向左移动1)
b = 0并且k> =存储在左子节点中的值:当前节点变为右子节点,k = k-左子节点的值,a = 2 * a + 1
b = 1且k <存储在右子节点中的值(1位分支,由于异或运算,所有内容都被翻转):当前节点变为右子节点,a = 2 * a
b = 1并且k> =存储在右子节点中的值:当前节点变为左子节点,k = k-右子节点的值,a = 2 * a + 1
再次是O(1),因为位数是恒定的。因此,总体复杂度为O(N + Q)。
示例:[0、1、4、5、7],即[000,001,100,101,111],k = 3,x = 3,即011
第一位为0并且k> = 2,因此我们继续,k = k-2 = 3-2 = 1且a = 2 * a + 1 = 2 * 0 + 1 = 1。
第二位是1并且k> = 1,因此我们向左移动(因为该位是1,所以求反),k = k-1 = 0,a = 2 * a + 1 = 3
第三位是1并且k <1,所以解是a = 2 * a + 0 = 6
控制:[000,001,100,101,111] XOR 011 = [011,010,111,110,100]即[3,2,7,6,4]和在顺序[2,3,4,6,7],因此索引3的数字确实是6和解(这里总是谈论基于0的索引)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句