Найти элемент Возникновение b раз в массиве размером n * k + b

Описание

Учитывая массив размером (n*k+b), где n элементов встречаются k раз, а один элемент встречается b раз, другими словами, существуют n+1 отдельные элементы. Учитывая, что 0 < b < k найдите элемент, имеющий b раз.

Мои предпринятые решения

Очевидное решение будет использовать хеширование, но оно не будет работать, если числа очень большие. Сложность O(n)
Использование карты для хранения частот каждого элемента, а затем перемещения карты, чтобы найти элемент, возникающий b раз. Поскольку Карта реализована как сбалансированные по высоте деревья, сложность будет O(nlogn).

Оба моего решения были приняты, но интервьюер хотел линейного решения без использования хэширования и намека, которые он дал, чтобы высота дерева была постоянной в дереве, на котором вы храните частоты, но я не могу найти правильное решение пока.

Я хочу знать, как решить эту проблему в линейном времени без хеширования?

EDIT:

Пример:

Вход: n=2 b=2 k=3

Aarray: 2 2 2 3 3 3 1 1

Выход: 1

Ответ 1

Идея с использованием циклических групп.

Чтобы угадать i-й бит ответа, выполните следующую процедуру:

Подсчитайте, сколько чисел в массиве имеет бит i-го бита, сохраните как cnt
Если cnt % k не равно нулю, то устанавливается i-й бит ответа. В противном случае это понятно.

Чтобы угадать целое число, повторите описанное выше для каждого бита.

Это решение технически O((n*k+b)*log max N), где max N - максимальное значение в таблице, но поскольку количество бит обычно является постоянным, это решение является линейным по размеру массива.

Нет хеширования, использование памяти O(log k * log max N).

Пример реализации:

from random import randint, shuffle

def generate_test_data(n, k, b):
    k_rep = [randint(0, 1000) for i in xrange(n)]
    b_rep = [randint(0, 1000)]
    numbers = k_rep*k + b_rep*b
    shuffle(numbers)
    print "k_rep: ", k_rep
    print "b_rep: ", b_rep
    return numbers

def solve(data, k):
    cnts = [0]*10
    for number in data:
        bits = [number >> b & 1 for b in xrange(10)]
        cnts = [cnts[i] + bits[i] for i in xrange(10)]
    return reduce(lambda a,b:2*a+(b%k>0), reversed(cnts), 0)

print "Answer: ", solve(generate_test_data(10, 15, 13), 3)

Ответ 2

Я предполагаю:

Элементы массива сопоставимы.
Мы знаем значения n и k заранее.
Решение O (n * k + b) достаточно хорошо.

Пусть число, имеющее только b раз, равно S. Мы пытаемся найти S в массиве размером n * k + b.

Рекурсивный шаг: Найдите медианный элемент текущего среза массива, как в Quick Sort в линейке. Пусть медианный элемент равен М

После рекурсивного шага у вас есть массив, где все элементы, меньшие, чем M, находятся слева от первого появления M. Все M-элементы расположены рядом друг с другом, и все элементы, большие, чем M, находятся справа от всех вхождений М.

Посмотрите на индекс самого левого M и вычислите, является ли S < M или S >= M. Перемещайтесь либо на левый срез, либо на правый срез.

Итак, вы делаете быстрый сорт, но в любой момент вносите только одну часть разделов. Вы будете перезаписывать O (logN) раз, но каждый раз с размером 1/2, 1/4, 1/8,.. размера исходного массива, поэтому общее время будет равно O (n).

Разъяснение:. Пусть говорят n = 20 и k = 10. Тогда в массиве имеется 21 отдельный элемент, 20 из которых встречаются 10 раз, а последнее происходит, скажем, 7 раз. Я нахожу элемент среды, допустим, это 1111. Если S < 1111, чем индекс самого левого вхождения 1111, будет меньше 11 * 10. Если S >= 1111, то индекс будет равен 11 * 10.

Полный пример: n = 4. k = 3. Массив = {1,2,3,4,5,1,2,3,4,5,1,2,3, 5} После первого рекурсивного шага я обнаруживаю, что средний элемент равен 3, а массив - примерно так: {1,2,1,2,1,2,3,3,3,5,4,5,5,4} Есть 6 элементов слева от 3. 6 кратно k = 3. Поэтому каждый элемент должен иметь место 3 раза. Итак, S >= 3. Считайте на правой стороне. И так далее.

Ответ 3

Чтобы иметь B-дерево с постоянной высотой, содержащее n различные элементы, с константой height h, вам нужно z=n^(1/h) детей на узлы: h=log_z(n), таким образом h=log(n)/log(z), таким образом log(z)=log(n)/h, таким образом z=e^(log(n)/h), таким образом z=n^(1/h).

Пример: n=1000000, h=10, z=3.98, то есть z=4.

Время достижения node в этом случае равно O(h.log(z)). Предполагая, что h и z должны быть "постоянными" (поскольку N=n.k, тогда log(z)=log(n^(1/h))=log(N/k^(1/h))=ct, правильно выбрав h на основе k, вы можете сказать, что O(h.log(z))=O(1)... Это немного надуманный, но, возможно, это именно то, что хотел услышать интервьюер?

Ответ 4

UPDATE: этот использует хэширование, поэтому это не очень хороший ответ: (

в python это будет линейное время (set удалит дубликаты):

result = (sum(set(arr))*k - sum(arr)) / (k - b)

Ответ 5

Если "k" четно, а "b" нечетно, тогда будет выполняться XOR.:)