Это очень простой вопрос для интервью. Поскольку вы знаете, что в первом наборе не более 1025 различных целых чисел, вы можете использовать это количество битов, чтобы указать, найдено ли каждое из этих чисел во входных наборах или нет. Итак, если вы хотите, чтобы ответ печатал каждое отдельное число ровно один раз, логика:
- Обнулить все 1025 битов в наборе битов A
- для каждого числа в первом наборе, установите соответствующий бит в A
- обнулить все 1025 битов в наборе битов B
- для каждого числа во втором наборе, установите соответствующий бит в B
- для i от 0 до 1024: если этот бит установлен как в A, так и в B, выведите i как часть вашего ответа
Теперь для создания набора битов из 1025 битов может не поддерживаться непосредственно ваш язык, поэтому вам иногда нужно использовать массив байтов, каждый из которых имеет 8 битов. Затем, скажем, вы хотите установить бит "k", вы найдете байт с индексом k / 8, а затем установите бит в позиции k% 8. Чтобы сделать последнее, вам нужно конвертировать из битовой позиции (от 0 до 7) в битовое значение (бит 0 представляет значение 1, бит 1, значение 2, бит 2, значение 4 ... бит 7, значение 128 - все степени двух). Чтобы получить эти значения, вы берете число 1 и сдвигаете его влево на «позицию бита». Итак, 1 << 0 по-прежнему 1, а 1 << 7 - 128. Затем вы можете: </p>
- спросить, включен ли этот бит в этот байт, с помощью сдвинутого значения со значением байта и проверки получения результата, отличного от 0, например в C и C ++:
if (array[k / 8] & (1 << (k % 8))) ...it's on...
- записать 1 в определенную битовую позицию в байте путем ИЛИ значения с байтом в C и C ++:
array[k / 8] |= (1 << (k % 8));
Существуют более эффективные способы сделать это, если в любом наборе окажется намного меньше 1025 значений, но это хорошее общее решение.