Previous Entry Share Next Entry
Тройка задач (и может быть перестановки)
ens_a_se
Встретил я тут несколько задач, которые, как мне кажется, имеют отношение к группе перестановок и, может быть, могут быть решены формально. Я же решаю их с помощью некоторых триков, для каждой задачи свой, рассматривая задачу как графовую.
Что есть перестановка на примере:
Возьмем двумерную матрицу nx2:|1 2 3 4 5|
|3 4 5 1 2|
Можем интерпретировать ее как пары, описывающие ребра в неком графе - (1,2), (2,4) etc
Так как всегда можно отсортировать первую строку, опустим ее и будем писать просто (3 4 5 1 2)
Над ними определена операция умножения - берем первое ребро из второй перестановки (1 3) и ищем ребро исходящее из 3ки в первом (3 2), записываем (1 2) и тп:
(4 3 2 1 5)(3 4 5 1 2) = (2 1 5 4 3)

Все задачи нужно решить за линую и без доп памяти, все числа целые, массивы не отсортированы
Задача 1
Дан массив из N чисел, каждое число из [1,N]. Некоторые элементы массива дважды встречаются в нем, некоторые 1 раз. Нужно найти все элементы из интервала [1,N] которых нет в этом массиве.
[Spoiler (click to open)]
Подсказка - присмотритесь к вершинам у которых нет входящих дуг


Задача 2
Дан массив из N+1 чисел, каждое число из [1,N]. Нужно найти дублирующиеся числа, если они там есть. Массив нельзя мутировать.
[Spoiler (click to open)]
Подсказка - найдите цикл и затем начало этого цикла


Задача 3
Дан массив из целых чисел (как отрицательных так и положительных), нужно найти первое пропущенное натуральное число. Например, [2,5,3,0,-1] - 1, [2,5,1,4,7,-1,-2] - 3 и так далее.
[Spoiler (click to open)]
Подсказка - идея как в первой

  • 1
представление в виде графа выглядит притянутым за уши. Лобовые решения 1 и 2 представляют собой hash_map<1..N, count> и проход по содержимому, что дает О(N). 3ю не понял что значит "пропущенное".

Ну а по памяти-то тоже дает линию. С графом можно сделать без доп памяти все три.

насчет фиксированной памяти будет любопытно теоретически. имхо практикческие решения с перфект хешом на массиве все победят =)

Да тут натуральные числа и диапазон известен, массив будет как перфект хэш таблица. На практике, через граф быстрее работает - это задача с leetcode, там показывается время на тестах и можно сравнить

ссылочка для ленивых есть?

сорри, сильно ленивым требующийся там логин не под силу =)
а, дошло через гугль. они в 1м перетирают массив. мгм. ну по условию можно, что тут сказать.

Edited at 2017-01-09 06:08 pm (UTC)

  • 1
?

Log in