K-й элемент в преобразованном массиве - PullRequest
Новая
       49

K-й элемент в преобразованном массиве

2 голосов
/ 21 октября 2019

Я столкнулся с этим вопросом в недавнем интервью:

Учитывая массив A длины N, мы должны ответить на Q запросов. Форма запроса выглядит следующим образом:

Учитывая x и k, нам нужно создать еще один массив B такой же длины, чтобы B[i] = A[i] ^ x, где ^ - оператор XOR. Сортировать массив B в порядке убывания и вернуть B[k].

Формат ввода: Первая строка содержит целое число N Вторая строка содержит N целых чисел, обозначающих массив A Третья строка содержит Q, то есть количество запросов. Следующая Q строк содержит пробел-разделенные целые числа x и k

Формат вывода: Вывести соответствующее значение B [k] каждое в новой строке для запросов Q.

например, для ввода: 

5
1 2 3 4 5
2
2 3
0 1

outputбудет: 

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

Я понятия не имею, как решить такие проблемы. Заранее спасибо.

1 Ответ

1 голос
/ 22 октября 2019

Это разрешимо в 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 возможности: смотреть на бит b в x и строить ответ a, который изначально равен 0:

  1. b = 0 и k <значение, сохраненное в левом дочернем элементетекущий узел (0-битная ветвь): текущий узел становится левым потомком, a = 2 * a (смещение влево на 1) </p>

  2. b = 0 и k> = сохраненное значениеу левого потомка: текущий узел становится правым потомком, k = k - значение левого потомка, a = 2 * a + 1

  3. b = 1 и k <значение, сохраненное вправый потомок (1-битная ветвь, из-за операции xor все переворачивается): текущий узел становится правым потомком, a = 2 * a </p>

  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 </p>

Управление: [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).

...