LINUX.ORG.RU

Нахождение повторяющихся элементов в массиве

 


0

8

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

Постановка задачи: Дан массив из n+1 элементов, в котором записаны числа от 1 до n. Отсюда ясно, что в этом массиве будет повторы. Необходимо найти это самое повторяющееся число. Повторяться оно может произвольное число раз.

Ограничения:

1) Время работы алгоритма: O(n);

2) Расход памяти: O(1);

3) Массив не изменяемый(immutable).

Я могу придумать решения за O(n^2), решение с использованием дополнительной памяти за O(n), решение с изменяемым массивом за то же самое O(n). Больше идей нет.

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

Ссылка на оригинал: Лекция №5. Время, с которого идет описание задачи: 00:09:10.

Дан массив из n+1 элементов, в котором записаны числа от 1 до n.

Сложить все числа, вычесть сумму чисел от 1 до n.

PolarFox ★★★★★ ()

Ну так надо найти повторяющееся число, а не повторяющиеся числа. В чем проблема-то?

geekless ★★ ()

Тьфу, тоже неправильно условие прочитал.

Имхо, условие в посте сформулированно криво. Щас по ссылке схожу, послушаю как там сформулировано...

geekless ★★ ()

Интересная задача. Где-то давно я ее решение читал. Вот только вспомнить не могу: то ли там во вспомогательной переменной XOR хранили, то ли циклический сдвиг. Но ключ — в использовании логических операторов.

Eddy_Em ☆☆☆☆☆ ()

Мне тоже кажется, что условие некорректно. Ну то есть эта задача с данными условиями (не обязательно присутствуют все числа от 1 до n, повторяться число может произвольное количество раз) и такими ограничениями не решаема.

unlog1c ★★★ ()
Ответ на: комментарий от unlog1c

Решаема. Но хитро. Кстати, количество повторов, ЕМНИП, найти нельзя. Можно лишь найти, какая цифра повторяется. И если повторяется больше одной цифры, решение ломается.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от geekless

Ну, то решение, которое я видел, было примерно так сформулировано: в массиве из M > N членов, которыми являются числа от 1 до N, повторяется одно число K. Найти это число за O(n) с использованием только O(1) дополнительной памяти.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от Eddy_Em

Я тоже думал о XORах. С ними есть такая закономерность (подобрал эмпирически): XOR 1..N равен:

  • N-1, если N mod 4 = 1
  • 1, если N mod 4 = 2
  • N, если N mod 4 = 3
  • 0, если N mod 4 = 0

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

unlog1c ★★★ ()

Дан массив из n+1 элементов, в котором записаны числа от 1 до n. Отсюда ясно, что в этом массиве будет повторы. Необходимо найти это самое повторяющееся число.

Повтор один, массив надо поксорить.

tensai_cirno ★★★★★ ()
Ответ на: комментарий от Eddy_Em

Кстати, количество повторов, ЕМНИП, найти нельзя.

Сча, второй раз пройти условие не запрещает.

anonymous ()
Ответ на: комментарий от anonymous

А ведь и правда: O(n) включает в себя и O(2n), и O(3n)…

Eddy_Em ☆☆☆☆☆ ()

Похоже это популярная задача на собеседованиях. Я сам не решил, но мне говорили решение. Если вспомню то скажу.

true_admin ★★★★★ ()

Короче, создай второй массив размера MAXINT и в нём считай повторы. По крайней мере в той задаче что мне говорили было оговорено что речь о 32-битных интах.

true_admin ★★★★★ ()
Ответ на: комментарий от true_admin

создай второй массив размера MAXINT и в нём считай повторы

Фу какая гадость. Что такое разрежённый массив вы не в курсе?

unlog1c ★★★ ()

(3) - самодеятельность?

Я могу придумать решения за O(n^2)

Два прохода 1. сортируешь 2. мегатривиальный поиск пары(или более) рядом стоящих чисел.

Первые два условия соблюдены. Трудоемкость O(N) Память O(1) Третье условие вообще непонятно откуда ты взял.

malbolge ★★ ()
Ответ на: комментарий от true_admin

расскажи дураку про разреженный массив с памятью O(1)

А массив размера MAX_INT - это по твоему О(1)?

Хотя да, логика есть, от N не зависит... правда только для задач, где N < MAX_INT.

unlog1c ★★★ ()
Ответ на: комментарий от unlog1c

я же указал для какой задачи я написал решение. Для данного случая оно не подходит, но может кого натолкнёт на решение.

Кстати, в голове что-то крутится про ксоры и хэши, попробую сформулировать...

true_admin ★★★★★ ()

Думал было, что решил задачку, но оказалось не все так просто. В общем, вот такая простая штука

#include <stdio.h>
main(){
	int X = 500;
	int i,j, res=0;
	for(j = 2; j < X; j++){
		for(i = 1; i <= j; i++)
			res ^= i;
		printf("N = %d, res: %d\n", j, res);
		res = 0;
	}
}
показывает, что XOR чисел от 1 до N идет четверками: [1, N+1, 0, N]. Спать уже пора. Но для чисел строго от 1 до N с одним повтором или одним пропуском можно легко найти решение, исходя из этого: вычислить, какая должна быть XOR чисел от 1 до N и XOR'ить ее с тем, что есть. Ответом и будет лишнее (если M = N+1) или недостающее (M=N-1) число.

Eddy_Em ☆☆☆☆☆ ()
Ответ на: комментарий от unlog1c

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

tensai_cirno ★★★★★ ()
Ответ на: комментарий от wota

Ты сейчас всю теологию к хуям сведёшь!

Дан массив из n+1 элементов, в котором записаны числа от 1 до n

Т.е., по твоим словам, имея массив c n=1000 элементов его можно сканировать 1000000000 раз и это будет все еще трудоемкость O(n). Правильно?

Объясни мне тогда, как у автора топика вышло O(N^2) ? Это, типа, лимит пробегов по массиву ограничен N^(N^N) ? Или как?

malbolge ★★ ()
Ответ на: комментарий от malbolge

Т.е., по твоим словам, имея массив c n=1000 элементов его можно сканировать 1000000000 раз

нет конечно, хватит бредить

wota ★★ ()
Ответ на: комментарий от wota

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

Вот-вот, прекращай.

malbolge ★★ ()

Привет,

ну тут вообще нечего решать при следующих допущениях: (1) числа в массиве целые от 1 до n (2) повторное число одно. Тогда любой школьник скажет что \sum_{i=1}^{n} = n (n + 1) / 2. Стал быть надо посчитать сумму иммутабельного массива и вычесть сумму, что и даст искомое число.

anonymous ()
Ответ на: комментарий от tensai_cirno

Дан массив из n+1 элементов, в котором записаны числа от 1 до n.

есть ссылка на видео - там четко спросили, и четко ответили

wota ★★ ()
Ответ на: комментарий от anonymous

Блин, вычесть \sum_{i=1}^{n}. В матном лабе sum(x) - n * (n + 1) / 2.

anonymous ()
Ответ на: комментарий от ebantrop

повторово может быть больше 1го

anonymous ()
Ответ на: комментарий от true_admin

Radix Sort. Он же поразрядная сортировка, есть в Кормене, если не изменяет память, работает с константной памятью. Могу ошибаться.

TheKnight ★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.