转换数组中的第K个元素 [英] Kth element in transformed array

问题描述

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

I came across this question in recent interview :

给出长度为<$ c $的数组 A c> N ，我们应该回答 Q 个查询。查询形式如下：

Given an array A of length N, we are supposed to answer Q queries. Query form is as follows :

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

Given x and k, we need to make another array B of same length such that B[i] = A[i] ^ x where ^ is XOR operator. Sort an array B in descending order and return B[k].

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

Input format : First line contains interger N Second line contains N integers denoting array A Third line contains Q i.e. number of queries Next Q lines contains space-separated integers x and k

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

Output format : Print respective B[k] value each on new line for Q queries.

例如
作为输入：

e.g. for input :

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 。

For first query, A = [1, 2, 3, 4, 5] For query x = 2 and k = 3, B = [1^2, 2^2, 3^2, 4^2, 5^2] = [3, 0, 1, 6, 7]. Sorting in descending order B = [7, 6, 3, 1, 0]. So, B[3] = 3.

对于第二个查询，
A 和 B 将与 x = 0 相同。因此， B [1] = 5

For second query, A and B will be same as x = 0. So, B[1] = 5

我不知道如何解决此类问题。

I have no idea how to solve such problems. Thanks in advance.

推荐答案

这可以在O（N + Q）中解决。为简单起见，我假设您只处理正数或无符号值，但是您也可以针对负数调整此算法。

This is solvable in O(N + Q). For simplicity I assume you are dealing with positive or unsigned values only, but you can probably adjust this algorithm also for negative numbers.

首先，您要构建一个二叉树。左边缘代表0，右边缘代表1。在每个节点中，您存储此存储桶中有多少个数字。可以在O（N）中完成，因为位数是恒定的。

First you build a binary tree. The left edge stands for a bit that is 0, the right edge for a bit that is 1. In each node you store how many numbers are in this bucket. This can be done in O(N), because the number of bits is constant.

因为这有点难以解释，所以我将展示如何树看起来像3位数字[0、1、4、5、7]，即[000、001、100、101、111]

Because this is a little bit hard to explain, I'm going to show how the tree looks like for 3-bit numbers [0, 1, 4, 5, 7] i.e. [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：

To answer a single query you go down the tree by using the bits of x. At each node you have 4 possibilities, looking at bit b of x and building answer a, which is initially 0:

1. b = 0且k<存储在当前节点（0位分支）的左子节点中的值：当前节点成为左子节点，a = 2 * a（向左移动1）

1. b = 0 and k < the value stored in the left child of the current node (the 0-bit branch): current node becomes left child, a = 2 * a (shifting left by 1)

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

b = 0 and k >= the value stored in the left child: current node becomes right child, k = k - value of left child, a = 2 * a + 1

b = 1并且k <存储在右子节点中的值（1位分支，由于异或运算，所有内容都被翻转了）：当前节点成为右子节点，a = 2 * a

b = 1 and k < the value stored in the right child (the 1-bit branch, because of the xor operation everything is flipped): current node becomes right child, a = 2 * a

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

b = 1 and k >= the value stored in the right child: current node becomes left child, k = k - value of right child, a = 2 * a + 1

这也是O（1），同样是因为位数是恒定的。因此，总体复杂度为O（N + Q）。

This is O(1), again because the number of bits is constant. Therefore the overall complexity is O(N + Q).

示例：[0、1、4、5、7]，即[000、001、100、101， 111]，k = 3，x = 3，即011

Example: [0, 1, 4, 5, 7] i.e. [000, 001, 100, 101, 111], k = 3, x = 3 i.e. 011

1. 第一位为0，k> = 2，因此我们开始对，k = k-2 = 3-2 = 1且a = 2 * a + 1 = 2 * 0 +1 = 1。

1. First bit is 0 and k >= 2, therefore we go right, k = k - 2 = 3 - 2 = 1 and a = 2 * a + 1 = 2 * 0 + 1 = 1.

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

Second bit is 1 and k >= 1, therefore we go left (inverted because the bit is 1), k = k - 1 = 0, a = 2 * a + 1 = 3

第三位是1并且k < 1，因此解决方案是a = 2 * a + 0 = 6

Third bit is 1 and k < 1, so the solution is a = 2 * a + 0 = 6

控制：[000，001，100 ，101，111] xor 011 = [011，010，111，110，100]即[3，2，7，6，6，4]并按[2，3，4， 6 7]，因此索引3的数字确实是6和解（这里总是谈论基于0的索引）。

Control: [000, 001, 100, 101, 111] xor 011 = [011, 010, 111, 110, 100] i.e. [3, 2, 7, 6, 4] and in order [2, 3, 4, 6, 7], so indeed the number at index 3 is 6 and the solution (always talking about 0-based indexing here).

这篇关于转换数组中的第K个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！