За линейное время и за константную доп память

массив получается c n-2 элементами

2 прохода это тоже линейное время

за один проход нужно?

0..n |> Enum.reject(&(Enum.member?(shuffled, &1)) за сколько работает? За n^2 ??

похоже на то

Осталось найти решение за C^n

за линейное время достаточно просто, а вот за один проход с константной памятью

первый проход - строим хэш с ключами от 1 до N второй идём по данным, выкидываем из хэша попавшиеся ключи оставшиеся невыкинутыми ключи в хэше искомые

как за один, непонятно

Ну

Один или два прохода не принципиально

Это линейное время

Проблема что словарь нельзя

Это не константная доп память

Константная - это несколько переменных все из которых ты будешь знать заранее

На этапе компиляции грубо говоря

А если идти по индексам значений?

Массив рамером N - константная память

Ща из толчка выду - бумажку возьму

вместо ключей словаря - индексы в массиве

Так не

Массив N - не константная, а линейная память

Размером n то константная

Если ты знаешь н

Давай чтобы проще было скажу что читаем массив из файла

И вся остальная память кроме этого массива должна быть константная

По индексам значений идти интересно но решения в этой стороне я не вижу

Может оно там есть

Это линейное время

Линейное время это же время которое увеличивается с размером входных данных, разве нет?

Ну да

Как раз проход

Или два прохода

Это оно и есть

N проходов по массиву длины N

Это уже не линейное время

А квадратичное

так отсортировать можно за линейное время наверное

Неа

Сортировка лучшая это n*log n

если n чисел в массиве n размера размешаны

от 1 до n

мы можем для каждого числа сразу его место определить

И запомнит

Да

Будет доп память

Не подходит

зачем запоминать

проходим по массиву два раза и ставим числа на нужные места

угу, это красиво

Короче говоря, для одной переменной: N - Сумма разностей индекса элемента и значения

Не спрашивайте как я это посчитал

Сумма разностей и

К примеру 3 0 1

Тогда n = 4

Ну да

И тд

Это правда

Типа сумма чисел от 1 до н

Сумма индексов от 0 до н-1

По сути то же самое

Сумма разностей н

Все верно

Но это ток для одного работает

Да, в том то и дело (

Короче, есть Варик считать все что возможно

Нафигачить тестовых данных, однословный персепторнчик

ERROR: S client not available

А потом погонять и посмотреть что сильнее всего влияет

)

Не

Персептрончик только в линейно разделимые данные умеет

Рандомно перемешанные числа не линейно разделимы

проходим по массиву два раза и ставим числа на нужные места

А почему вот это не подходит?

нужно найти числа n+ 1, n+ 2 и удалить и вместо них записать -1, а потом пройтись еще два раза и расставлять числа на индекс соответствующий значению числа, и пропускать -1

Потому что общо слишком

Не алгоритм это

Не получается так

очень даже алгоритм

Ты не знаешь какие числа куда ставить

Ну тут ответ универсальный

Попробуй заполнить

Запрогать

Увидишь)

Ща

То есть берем первое число, ставим его на его место по индексу, оттуда берем что было и ставим тоже на его место и тд

Это ты сортировку описываешь

У тебя вылезут н проходов

А не 2 прохода

кто?

Потому что ты не знаешь кккие числа ставить на место пока все не поставишь

Потому что ты не знаешь кккие числа ставить на место пока все не поставишь

Так мы же знаем куда ставить

вот смотри

у тебя массив размера n

Не получается

Так

То есть 100 мы ставим на индекс 100

макс число в нем n+ 2

a[100]=100