转换数组中的第 K 个元素
Kth element in transformed array
我在最近的采访中遇到了这个问题：
给定一个长度为 N 的数组 A，我们应该回答 Q 个查询。查询表格如下：
给定 x 和 k，我们需要创建另一个长度相同的数组 B，使得 B[i] = A[i] ^ x 其中 ^ 是 XOR 运算符。对数组 B 进行降序排序，return B[k].
输入格式：
第一行包含整数 N
第二行包含 N 个整数，表示数组 A
第三行包含 Q 即查询数
接下来 Q 行包含 space 分隔的整数 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
我不知道如何解决这些问题。提前致谢。
这在 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 and k < 当前节点左child存储的值（0位分支）：当前节点变为左child，a = 2 * a（左移1）
b = 0 and k >= 左存储的值child: 当前节点变为右child, k = k - 左的值child, a = 2 * a + 1
b = 1 and k < the value stored in right child (1-bit branch, because of the xor operation all is flipped): 当前结点变为右 child, a = 2 * a
b = 1 and k >= the value stored in the right child: 当前节点变为左child, k = k - 右的值child, 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
Control: [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 的索引）。
我在最近的采访中遇到了这个问题：
给定一个长度为 N 的数组 A，我们应该回答 Q 个查询。查询表格如下：
给定 x 和 k，我们需要创建另一个长度相同的数组 B，使得 B[i] = A[i] ^ x 其中 ^ 是 XOR 运算符。对数组 B 进行降序排序，return B[k].
输入格式： 第一行包含整数 N 第二行包含 N 个整数，表示数组 A 第三行包含 Q 即查询数 接下来 Q 行包含 space 分隔的整数 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
我不知道如何解决这些问题。提前致谢。
这在 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 and k < 当前节点左child存储的值（0位分支）：当前节点变为左child，a = 2 * a（左移1）
b = 0 and k >= 左存储的值child: 当前节点变为右child, k = k - 左的值child, a = 2 * a + 1
b = 1 and k < the value stored in right child (1-bit branch, because of the xor operation all is flipped): 当前结点变为右 child, a = 2 * a
b = 1 and k >= the value stored in the right child: 当前节点变为左child, k = k - 右的值child, 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
Control: [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 的索引）。