бамп
Можно сделать за один проход с выделением памяти под ещё один такой же массив. Итерируешь исходный массив, во второй массив кладешь 1 по индексу значения этого элемента. Если там уже есть 1 - значит повтор
for i 1 to n+1 do
Begin
For j 1 to n+1 do
if a=a[j] then inc(k);
if k>1 then write (a, 'повторяется');
k:=0;
End;
Begin
For j 1 to n+1 do
if a=a[j] then inc(k);
if k>1 then write (a, 'повторяется');
k:=0;
End;
После if a(i), макаба кушает квадратные скобки
>Линейное время
>Вложенные циклы
Сортируешь, в цикле сравниваешь два рядом стоящих.
Или выделяешь еще один массив и ++ по индексу.
Я не ебу что такое линейное время.
Я заметил, ебанат ленивый
> Сортируешь
> линейное время и константу памяти
Массив будет не такой же, а размером с максимальное число.
Надеюсь не будущий программист.
А так, очевидный хэш-подход. Если число ограниченно, тупо делаешь второй массив, как писал первый чувак.
Посмотри как мультимножества зделоны, ихние экземпляры такими подсчетами занимаются. collections.Counter в python, например.
Ты долбаеб? Констанстная память? Какое нахуй хеш еблан?????
Еблан тупой блядь, иди на хуй из моего IT.
Подсказка - пройтись XOR-ом.
Хеш не бывает константным?
Дурацкий двач. Ну так что, уёбок? Чем тебе развернуть массив на максимальное число не константно? Хэш-функция F: x->x. Это же не метод цепочек какой-нибудь.
Кретины, блядь.
https://pastebin.com/tnhNKhra
https://pastebin.com/tnhNKhra
>Все числа принимают значения от 1 до N
Суммируешь массив, затем вычитаешь из него сумму чисел от 1 до N (формула n*(n-1)/2), получаешь искомый ответ.
> Еблан тупой блядь, иди на хуй из моего IT.
> Подсказка - пройтись XOR-ом.
Сам пройдись, довен. О результатах доложишь.
> Повторений может быть сколько угодно.
Ещё один дебил
Массив чисел можно отсортировать за линейное время. Radix sort, все дела.
>массив на N
Нормально
Ну так он прав же. Ассоциативность ксора.
-кун
сортируешь масив любым из способов
сравниваешь предыдущее и следущее, если совпадают выписваешь в третий масив
За сколько памяти, еблан
Три массива
ОХУЕННО
повторений сколько угодно. Бляяяя, откуда вы дауны лезете?
Это как, блядь? У тебя по условию может повторяться только одно число (одно - 1). Или ты хочешь сказать, что одно число может повторяться несколько раз?
А вот это не помню.
Вообще вангую что у задачи нет решения, тут раньше был такой анон, который создавал подобные треды с нерешаемой задачкой, пока наконец кто-то не накормил его хуями с пруфами что решить ее невозможно с теми ограничениями памяти и времени что он указывал.
Ну и высер
1
Да как так блядь? Если число ограниченно, то всё есть. Как сортировка повтором.
хэш-кун
Окей, да.
Надеюсь тебя к кодерству не подпустят с такой писаниной
Где он прав, блядь? Ксор поможет только если в массиве все числа имеют пару, кроме одного искомого. Тогда ксор уберёт пары и останется результат. У опа задача совершенно противоположная.
Квиксорт с тремя партишнами. = O(n)
Проходимся по массиву и проверяем єлемент с предидущим = O(n)
2O(n) = O(n)
Правда костанта памяти не війдет, так как квиксори O(n)
> Или ты хочешь сказать, что одно число может повторяться несколько раз?
Это. Я не оп, но других вариантов я не вижу.
Я в гугле работаю, хуйлоблядь.
Единственное правильное решение кстати.
>Квиксорт с тремя партишнами. = O(n)
>Квиксорт
>O(n)
Мы вам не перезвоним, уебывайте.
мимо-разработчик-в-IT-компании
По делу есть, что сказать, или кукарекание только?
мы вам перезвоним, если коротко
Аноны, откуда начать учить кодинг на питоне, что бы понимать о чем вы трёте в треде?
> кококо
Я понял.
Спиздил моё решение, да так, что стало нечитаемо вообще. Молодец.
Я не спиздил. А взял с сасайта, который мне рекомендовал вот этот чувак. geeksforgeeks.org
Поясни механику решения. Я ее не совсем могу раздуплить.
Мы пробегаемся от 1 до N, берем элемент массива, стоящего по этому номеру, затем берем элемент массива, стоящего по номеру предыдущего элемента и умножаем на -1, а затем проверяем, что если элемент больше нуля - то он повторяется. Почему оно работает?
Здесь нету никакой логики. Это как олимпиадные задачки. Где нужно найти хакерское решение из предоставляемых данных. Ок, есть всякие разделяй-охуевай, динамическое программирование, метод ветвей и границ, бектракинг, рекурсия, гридди-алгоритмы, битовая магия, однопроходные алгоритмы. Тут нет логики. Ты сам должен её придумать, опираясь на свои знания и опыт в построении алгоритмов.
- кун
Но если оно работает - то на чем-то основано решение. На математическом факте там, да хотя бы просто детализируй алгоритм.
Да, я даун. Уже писал выше.
{1 2 3} сработает на таком алгоритме?
i = 0
a = 1
a[1] = 2
a[1] := -2
i = 1
Повторяется 2. Как так?
Не важно. В задании сказано, что повторения есть всегда.
Смотри, если бы не было ограничения на память, то задача решалась бы так. Есть массив чисел от 0 до N. Мы выделяем массив размером N и заполняем его нулями. Далее итерируем по исходному массиву и для каждого встреченного числа m мы увеличиваем счётчик во втором массиве по индексу m на единицу. Та ячейка массива, где значение больше единицы, соответствует числу, которое повторялось. Поскольку у опа есть ограничение на память, мы можем использовать исходный массив для хранения счётчика (вернее, его кастрированной формы - видели число чётное количество раз - знак плюс, нечётное - минус). Поскольку нас интересуют только значения 1 (не повторяется) и 2 (повторяется как минимум два раза), этого достаточно.
Вот теперь понял. Ты охуеннен.
Спасибо :3
Ебать.
А если повторяется четыре раза, то хуйня будет.
Это си плюс ебаное, там массивы с 1 нумеруются.
А мы не ждём, что оно четыре раза повторится. Повторилось два - давай досвиданье, ответ готов.
А кто-нибудь уже предлагал тупо сложить все числа в массиве?
Пиздец вы тупые.
Сложить всё и вычесть N*(N+1)/2.
Всё. Время линейное, память константная.
Сложить всё и вычесть N*(N+1)/2.
Всё. Время линейное, память константная.
Ту так это сразу "мы вам перезвоним" же.
И переполнение типа более чем на 90% случаев
У тебя "больше чем в 90% случаев" массивы больше 2^32 элементов?
Ну хорошо - тогда уточнение: выполнять все операции по модулю P, где P > N+1 и не делится на 2.
Сделай это на массиве
1 2 3 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 9 10
Условиям задачи он удовлетворяет.
Успехов, кек.
Триггер тут "Сложить всё". Меня однажды завалили на этой задачке в яндексе, когда устраивался. Сказали мол переполнение будет, досвидос.
Берем переменную-аккумулятор равную нулю.
Пробегаемся по массиву и ксоким аккумулятор с индексом элемента и со значением по этому индексу.
В перле не будет.
Просуммировал всё и вычел n(n+1)/2, получил результат.
Нихуя не понял.
Возьмем массив [1, 1, 1]
Просуммируем, получится 3.
Вычитаем 3(3+1)/2, получается 6.
ЧЯДНТ?
то есть получается -3.
>Нужно указать, какой элемент в массиве повторяется.
А вообще вы похоже неправильную задачу решаете.
Нужно указать элемент, а не значение. То есть ответом должны быть индексы.
А вообще вы похоже неправильную задачу решаете.
Нужно указать элемент, а не значение. То есть ответом должны быть индексы.
>Возьмем массив [1, 1, 1]
Так ты бери который имеет смысл по условию.
n = 3,
{1,2,2}
1+2+2 = 5
3(4)/2 = 6
6-5 = 1
1+5 = 6
6/2 = 3
Ответ: третий элемент.
ОЧЕВИДНО ЖЕ
>третий элемент
>третий
Но тут только нулевой, первый, и второй.
Бля, я решил.
for i in array:
array.pop(i)
if i in array:
print(i)
for i in array:
array.pop(i)
if i in array:
print(i)
Время не константное.
За питонизм получаешь золотого змея. За него же получаешь кресты точены на стул.
В условии сказано что количество повторений может быть любым.
Из этого следует что числа не обязаны принимать каждое значение, они только МОГУТ.
>if i in array:
Тут неявно O(n). Общее время будет O(n^2).
Не говоря уже что нельзя менять длину листа когда обходишь его
Тогда это не решается.
Что значит константное/неконстантное время? Я не погромист.
>нельзя менять длину листа когда обходишь его
Кто мне запретит?
Идиот слепой, выше уже всё решили.
>>> a = [0,1,2]
>>> for i in a:
... a.pop(i)
...
0
Traceback (most recent call last):
File "<console>", line 2, in <module>
IndexError: pop index out of range
>Кто мне запретит?
Аллах.
>https://ideone.com/dsYRDh
Ты про эту хуйню? За такой код в продакшене тебя отпиздят после работы. Код должен быть читабельным, а не макачьими плясками. Уволен нахуй, уёбок.
for i in array:
if i in array.pop(i):
print(i)
а так?
Всё читаемо же, если ты не довн.
Мимо
Очевидное TypeError: argument of type 'int' is not iterable
Ты толстишь что ли?
Нет, не читаемо, все хуита, а ты дебил и позер. Пошел на хуй.
Но ведь если ты не можешь прочитать простенький код, то дебил - это ты. Зачем вообще ты сидишь в треде по алгоритмам? Пиши на пыхе что-нибудь, запихивай данные в базу. На это ты сгодишься.
Почему сразу толстишь, я просто эникейщик.
n = rand(1,100);
a = generate_rand_array(1,n);
for i 1 to n+1 do
{
if (a > n) {
z = a - n;
} else {
z = a;
}
if (a[z] > n) { echo i . 'пиймав на вила'; }
else {a[z] = a[z] + n}
}
не прогонял. z - твоя константа, время линейное
n = rand(1,100);
a = generate_rand_array(1,n);
for i 1 to n+1 do
{
if (a > n) {
z = a - n;
} else {
z = a;
}
if (a[z] > n) { echo i . 'пиймав на вила'; }
else {a[z] = a[z] + n}
}
быстрофикс
сука йобаная вакаба не ест скобочки с i
n = rand(1,100);
a = generate_rand_array(1,n);
for p = 1 to n+1 do
{
if (a[ p ] > n) {
z = a[ p ] - n;
} else {
z = a[ p ];
}
if (a[ z ] > n) { echo i . 'пиймав на вила'; }
else {a[ z ] = a[ z ] + n}
}
Ну напиши ты в ideone или в wepaste хотя бы.
Вроде должно работать, наверно. Принцип как тут.
Оп-хуй, пили ещё задач. Годно.
Это не питона вопрос, а алгоритмов.
Python Algorithms isbn: 978-1-4302-3238-4
Что значит какой элемент повторяется? Что если несколько элементов повторяются?
Суммируешь все элементы массива
Вычитаешь из массива сумму от 1 до N
По условию повторяется только один.
>Вычитаешь из массива сумму от 1 до N
из суммы, конечно же
Не знаю ОП тут ли ты. Решается хэш таблицей. Хэш таблица это такая штука... короч, в шарпе есть хэш таблица и при добавлении в нее элемента, она (функция Add) выдает тру если элемент в таблице уже был. Считаешь Тру перебором значений первичного массива. Радуешься жизни.
добавлю. хэш таблица выдает за О(1), поэтому при n элементах получается ровно линейное время.
> и константу памяти
И тут ты соснул с проглотом
Бля, ебать ребята вы умные. Как стать таким же?
Чот взлольнул. И ведь работает.
а нихуя. у тебя может быть дохуя повторений одного числа
По условию не может.
Ах ты ж блядь, в глаза долблюсь. Ну ладн.
Циклически проходишь по массиву, каждый непосещенный элемент a ставишь на место a[a], элемент с его места переставляешь так же. Когда очередное попадает в ячейку, где стоит такое же число, как и должно быть, ты нашёл повтор (одно число стоит на месте, другое ты переместил). Линейное время работы (одна операция с каждым элементом), две переменные (указатель на элемент массива и временная переменная).
Двач портит разметку. Каждый элемент массива перемещаешь в ту ячейку, индексом которой является значение этого элемента.
у нас есть победитель
Иксором все элемнты проходишься и получаешь ответ, задача для 5б класса.
Лоллирую. Когда вместо программирования используют логику.
Лол, когда не знают, как описывают алгоритмы.
Ну, вот если бы оно работало для произвольных чисел а не для [1..n], вот тогда это хотя бы как-то можно было назвать. Охуеть, блядь, алгоритм.
ты довн, оно и должно работать для [1..N]
ТИМЛИД ВРЫВАЕТСЯ В ПОМЕЩЕНИЕ
@
СЫЧЁВ БЛЯДЬ СРОЧНО У НАС ПРОЕКТ НЕ ЗАКРЫТ ПИШИ ЕБАНЫЙ МОДУЛЬ
@
КИДАЕТ ТЗ НА СТОЛ, ЗАТЯГИВАЕТСЯ ВЕЙПОМ, ХЛОПАЕТ ДВЕРЬЮ
@
ВЕЧЕРОМ ВВАЛИВАЕТСЯ В ОФИС, ПРОСИТ ПОКАЗАТЬ, ЧТО СДЕЛАЛ ЗА ДЕНЬ
@
А НУ НОРМ НО ЧОТ МОГЛО БЫТЬ ЛУЧШЕ, ТЫ НЕ МОГ СДЕЛАТЬ ЧТОБ ПОД ЛЮБЫЕ ВХОДНЫЕ РАБОТАЛО А НЕ ТОЛЬКО КАК В ТЗ?
@
ПРЕМИЮ ТВОЮ ВЫПИШУ НА СЕБЯ
лел. конечно собъется когда вдруг на месте i сгенерится число i.
создаешь зануленный массив длинной N+1
проходишь по оригинальному массиву, i во втором массиве сравниваешь с нулем. если да - меняешь на единичку, если нет - каунтер повышаешь на единичку.
Но алгоритм потом вбиваете же в какой-нибудь язык программирования
а вероятность первого пункта - 1- (n!)/(n)^n
что по формуле Стирлинга стремится к 1 для больших n. Учи матан
пардон ый элемент
iтый блять
и тервер.
myarray = ()
foreach(array as elem){
if( not_in_array( myarray, elem ) ) {
myarray[elem]++
}
}
unset(myarray, elem = 1)
foreach(myarray as key val){
print key 'повторяется' val 'раз'
}
Я не прав. Тот парень со сменой элементов прав. Сорян. Красавчик че.
Я не прав. Тот парень со сменой элементов прав. Сорян. Красавчик че.
Складываешь все числа, считаешь сумму от 1 до n по формуле, вычитаешь из первого второе
>N+1
>от 1 до N
Ебать ты тупой. То есть, допустим у нас есть масив длиной 6 (N=5) с числами 1 2 3 4 5? Где ещё одно число, сучка?
Хуя ты довен.
Единственно что нужно добавить. Что после сравнения и перемещения нужно снова проверить перемещенный с того места элемент и если его i не совпадает - переместить(т.е. запустить рекурсию по элементу до тех пор пока либо не переберется весь массив (тогда значение в ячейкие совпадет с порядковым номером) либо пока не найдём равное значение. Тогда из рекурсии выходим и идём к следующему элементу
[eq
>1 2 3 4 5
Может быть и
1 2 3 4 5 5
и
1 2 3 4 4 4
Суммируешь все элементы и вычитаешь сумму от 1 до N
thread ne chital
thread ne chital
Бля, я даун, они ж повторяться могут
Бля я думал это по порядку типа [1; N] (что даже читается "от единицы до N").
Блять нельзя написать "каждое число". Взяли написали "все числа".
Если в массиве повторяется только одно число, а все остальные от 1 до Н, то элементарно - считаем за константу арифметическую последовательность от 1 до Н, затем за линейное время считаем сумму всех элементов и за константу вычитаем одно из другого. Это ответ.
еще один тред не читал. довен
>N+1
>от 1 до N
>Повторений может быть сколько угодно
Нет, в таком случае повторение может быть только одно.
>1 2 3 4 4 4
Не может, потому чтов этом нет 5
может не быть пятерки. единственное ограничение на массив - элементы не превосходят N
Я не кодер, но задача показалась мне интересной.
Что значат 2 условия в ОП посте?
Что значат 2 условия в ОП посте?
сверяешь первый со вторым и до конца массива - учитываешь результат (строишь алгоритм так чтоб при совпадении не попало в повторное сравнение).
сверяешь второй с третьим и до конца массива (строишь алгоритм так чтоб при совпадении не попало в повторное сравнение).
и так далее.
сверяешь второй с третьим и до конца массива (строишь алгоритм так чтоб при совпадении не попало в повторное сравнение).
и так далее.
У любого алгоритма (обычно имеется ввиду однообразно повторяющиеся, циклические штуки) есть сложность. Например, если обработка 10 элементов (цифр, например) требует 100 циклов вычислений, то алгоритм имеет степень сложности nn - квадратичный. "Линейная" сложность - это когда на n элементов нужно n+a или, в худшем случае, na при a<n циклов.
Константа памяти - конкретно здесь значит хуйню, но в общем случае имеется ввиду, что памяти для решения выделяется конечное количество, причём логически "подходящее" под условие задачи, чтобы для итерации 10 целочисленных значений твоей проге не требовалось 10 Гб памяти.
Блядская разметка.
>конкретно здесь значит хуйню
Конкретно здесь это означает, что нельзя создать контейнер размера N, в котором отмечать, встречалось такое число или нет.
>"Линейная" сложность - это когда на n элементов нужно n+a или, в худшем случае, na при a<n циклов.
А вот тут какая?
Ещё немного, и будет "пузырёк".
очень хорошо, а что мы делаем когда все биты заняты чем-то полезным.
Достаточно попробовать выстроить массив по порядку. Если a != i, то меняем местами элементы a и a[a], если они равны, то печатаем результат и выходим
Ой, извините, совсем хуйню написал, не читайте, пожалуйста.
Хохлогромист
Нужно это сделать за линейное время и константу памяти