变换数组中的第K个元素

Question

我在最近的采访中遇到了这个问题：

给定长度为A的数组N，我们应该回答Q查询。查询形式如下：

给出x和k，我们需要制作另一个相同长度的数组B，使得B[i] = A[i] ^ x其中^是XOR运算符。按降序对数组B排序，然后返回B[k]。

输入格式：第一行包含整数N第二行包含N个表示数组A的整数第三行包含Q，即查询数量接下来的Q行包含以空格分隔的整数x和k

输出格式：在Q行查询的新行上分别打印各自的B [k]值。

例如输入：

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

我不知道如何解决此类问题。预先感谢。

Answer 1

这在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：

1. b = 0且k

2. b = 0且k> =存储在左子节点中的值：当前节点变为右子节点，k = k-左子节点的值，a = 2 * a + 1

3. b = 1并且k

4. 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

1. 第一位是0且k> = 2，因此我们去对了，k = k-2 = 3-2 = 1且a = 2 * a + 1 = 2 * 0 + 1 = 1。

   ] >

2. 第二个位是1且k> = 1，因此我们向左移动（因为该位是1，所以求反），k = k-1 = 0，a = 2 * a + 1 = 3

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的索引）。