Вот ты получаешь на n/2 итерации число n+2 Куда его ставить?

на первой итерации заменить n+1 и n+ 2 на -1

Нет в тот же самый. Ща попробую накидать на js, может правда туплю

Но это доп память

А если в этот же

То надо сделать что то с числом

Которое сейчас на 100 месте стоит

если n+1 нету, то оно одно из искомых и дальше все очевидно

Чисто пример 2 0 4

Сперва ты берёшь 2 и ставишь его вместо 4

Потом ты берёшь 4 и че?

Ответ в задаче - 1,3

if(a[i] != i) { swap(a[i], a[a[i]]) }

и так два раза пройтись

ну еще игнорировать -1

в итоге на месте чисел со значением -1 получим искомые

допустим массив размера 5, в нем есть число 7

ищем 6 и 7 заменяем их на -1

если нет 6 то оно одно из искомых

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

там где будут числа со значением -1 - индексы являются ответом

Так как ты заснуешь число если он за границей массива?

оно не будет за границей массива

потому что 7 и 6 там нет

Вообще говоря такое работает

ну и на -1 проверять

не забывать

Только надо 3 прохода и 3 доп переменные

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

адепты Plug, кто-нибудь вкручивал Ueberauth?

2 0 4 -1 -1 4 0 2 -1 -1 0 4 2 -1 -1 0 4 2 -1 -1 Второй 0 4 2 -1 -1 0 -1 2 -1 4 0 -1 2 -1 4 И третий чтобы подобрать индексы

только недостаток в том что алгоритм сложнее если выкинуть больше 2х чисел

Хм

Что то не понел

Вроде дельно

Ща сделаю питон

Но что то здесь не так)

И потестим

да все так

суть в том что для чисел не больше n мы знаем их позицию в отсортированном массиве

а если число больше n, то нам надо его как то обработать

поэтому и сортировка линейная

а хотите еще больше усложню? :)

N может быть больше чем int.maxValue

у нас пистон)

есть числа от 1 до N. два выкинули, все перемешали. память пользовать нельзя, решить за N/1000

есть числа от 1 до N. два выкинули, все перемешали. память пользовать нельзя, решить за N/1000

Могу решить за константное время с вероятностью (С из N по 2)^-1

N/1000 это что?

def solve, do: {0,1}

время решения должно быть кратно 5min*n где n множество чисел не упорядоченных по не возрастанию, натуральных чисел

задача не ясная какая-то

Короче в падлу петон, завтра сделаю

что можно, что нельзя. зачем всё это, все равно все умрем

на фоне всего этого, почему-то есть вот язык программирования, но в нем что-то нельзя

есть числа от 1 до N. два выкинули. вобщем объяснять некогда. дедлайн вчера.

Есть число от 1 до N. Дедлайн выкинули, два числа перемешали. Массив вчера

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

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

У меня такое было начальник даже премию выписал

нынче в индустрии принято подобные задачи на собесах задавать

Леща(

ты такой, ну может как-то мы как-то потратим всетаки память и решим задачу? нет! пы приняли санкции против производителей оперативной памяти и не имеем права использовать ОЗУ. иначе нас всех закроют

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

ну когда у тебя миллионы серверов, то код производительнее на 1% экономит миллионы долларов - то нужны разработчики которые задрачивают подобные задачи

тут где-то статья была про вреждевременную кхм

оптимизацию

Postgres летает, nginx отдрочен как хрен, а твой ActiveRecord делает select * а потом фильтрует(((

На каждую оптимизацию в 1% найдётся свой Джуниор

ERROR: S client not available

за константную память и еще памяти дают каких-нибудь 500Кб и ты думаешь - фублять, жлобы чёртовы (у самого то макбук и 16 гиг ОЗУ) и посылаешь их подальше.

подтверждаю. Mysql 10 лет назат на сраном селероне, с 256 памяти, при правильно расставленых индексах, чудесно решал бизнес задачу, где надо было выбирать из 10М записей 250 штук. и нормально укладывался в 0.01с, что даже на глаз затупа было не заметна. и смешно. было на дельфях. и до сих пор работает на реальном производстве

поэтому яндекс и гугл юзают цпп и требуют знания алгоритмов

а вот такие сферические задачи - мне не ясно. что там за последовательность такая и для чего

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

знания алгоритмов именно в контексте таких сферических задачек

я не знаю, как там в гуглах. я по жизни на производствах работал. а там базы данных. либо производственные, либо булгактерские. и там нет никакого смысла выдумывать какую-то хрень. самое главное освоить SQL

а нафига оно надо-то? задачи на практике чаще всего значительно отличаются от этих сферических ;)

какому нить стартапу конечно это не нужно, или в вебчике

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

какому нить стартапу конечно это не нужно, или в вебчике

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

сам наблюдал такое. ну вот не умеет человек рекурсию. и все.

сборку не сделает

сам наблюдал такое. ну вот не умеет человек рекурсию. и все.

чтобы понять рекурсию нужно понять рекурсию нужно понять рекурсию

у гугла раньше хорошая пасхалочка была.. жаль убрали

а кому-то не надо

я тут на хабре статью запилил. где на эликсире пару функций рекурсивных написал

чтобы понять рекурсию нужно понять рекурсию нужно понять рекурсию

...Нужно понять рекурсию, нужно понять ре... Programm Stack overflow(

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

...Нужно понять рекурсию, нужно понять ре... Programm Stack overflow(

поэтому мы за хвостовую рекурсию! и за её оптимизацию :)

+1

https://github.com/rust-lang/rust/issues/217

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

https://github.com/rust-lang/rust/issues/217

бедняги.. ну может оно им не надо. кайфуют с циклов

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

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

у нас как-то на работу взяли олимпиадника одного, только он месяц мычал и не мог раздуплить core data с блютусом под ios

бывает и такое

воот. есть о чем задуматься! и ты такой бамсь, и решил производственный вопрос, свел все данные в отчет. руководство получило результаты. как на приборной доске в машине. данные для принятия решения. и все счастливы. а на дельфи ты там решил или на Go, или на FoxPro - это все вообще побоку

какой там у тебя алгоритм. предполагаю, что знания библиотек тут быстрее поможет

так что решать от 1 до N это все как бы....

не, решать то прикольно, для себя, мозги потренировать

а вот на собеседовании такое спрашивать - нафиг надо