Re[2]: Поиск повторяющегося числа в массиве - Этюды для программистов

Здравствуйте, Аноним, Вы писали:

S>>Разве в условии сказано что N = M + 1?
S>>N = 10, M = 1000. Куда приложить прогрессию?

А>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
А>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.

У меня сначала тоже такая мысль была. Но я решил, что тогда бы не стали парить мозги и написали бы, что дан массив из M+1 чисел.
А вообще, интересно, откуда эта задачка взялась: если из института с лабораторной работы — это одно, если с крутой олимпиады по информатике — это другое

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

S>>>Разве в условии сказано что N = M + 1?
S>>>N = 10, M = 1000. Куда приложить прогрессию?

А>>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
А>>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.

A>У меня сначала тоже такая мысль была. Но я решил, что тогда бы не стали парить мозги и написали бы, что дан массив из M+1 чисел.
A>А вообще, интересно, откуда эта задачка взялась: если из института с лабораторной работы — это одно, если с крутой олимпиады по информатике — это другое

Парят специально — ты должен догадаться что N = M + 1.
Да нет задачка на сообразительность, на олипмиадную не тянет, максимум на школьную олимпиаду.
Меня спросили на собеседовании эту задачу — мое решение было как раз с прогрессией, они свой вариант не сказали, но я думаю что лучше ничего не придумаешь тут.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, -VladK-, Вы писали:

VK>>>Народ, да вы че?
VK>>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!

S>>Разве в условии сказано что N = M + 1?
S>>N = 10, M = 1000. Куда приложить прогрессию?

А>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
А>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.

N <= M + 1

1,3,101

M = 101
N = 3

все довольны, так что не катит

Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:
X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>число в этом массиве повторяется два раза. Найти это число за время O(N).

Самое простое выделить второй масив из M элементов
пройтись по по первому масиву N и в масиве M возвести флаг по значению, если флаг есть — то вот и оно

for( n in N ):
 if ++M[n] == 2:
  return n

а если без памяти порядка M нужно думать, ушел думать

Здравствуйте, IROV.., Вы писали:

Специально для Dufrenite.

IRO>

IRO>for( n in N ):
IRO> if ++M[n] == 2:
IRO>  return n
IRO>

Сколько стоит операция (n in N)?

Здравствуйте, IROV.., Вы писали:

IRO>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, samius, Вы писали:

S>>>Здравствуйте, -VladK-, Вы писали:

VK>>>>Народ, да вы че?
VK>>>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!

S>>>Разве в условии сказано что N = M + 1?
S>>>N = 10, M = 1000. Куда приложить прогрессию?

А>>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
А>>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.

IRO>N <= M + 1

IRO>1,3,101

IRO>M = 101
IRO>N = 3

IRO>все довольны, так что не катит

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

Здравствуйте, IROV.., Вы писали:

IRO>

Здравствуйте, Xobotik, Вы писали:

X>>Условие задачи:
X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
X>>число в этом массиве повторяется два раза. Найти это число за время O(N).

IRO>Самое простое выделить второй масив из M элементов
IRO>пройтись по по первому масиву N и в масиве M возвести флаг по значению, если флаг есть — то вот и оно

IRO>

IRO>for( n in N ):
IRO> if ++M[n] == 2:
IRO>  return n
IRO>

IRO>а если без памяти порядка M нужно думать, ушел думать

Если M большое то нехорошо выйдет, как более щадящий вариант можно массив флагов, но использовать как битовую маску — хотя тоже размер такого массива пропорционален M, хоть и меньше.

Здравствуйте, -VladK-, Вы писали:

VK>Если M большое то нехорошо выйдет, как более щадящий вариант можно массив флагов, но использовать как битовую маску — хотя тоже размер такого массива пропорционален M, хоть и меньше.

Специально для Dufrenite.

Остальные не могут встречаться 3 и более раза?

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Буравчик, Вы писали:

Б>>Нужна другая структура данных, от которой требуется:
Б>>- быстро проверять наличие элемента (на основе хэша)
Б>>- быстро добавлять новый элемент

Б>>>>1. Запутывает код.
X>>>Отнюдь.

Б>>Запутывает, потому что словарь используется не по назначению.

A>Да, конечно, в терминах C# надо вместо Dictionary использовать свежепоявившийся HashSet, совсем про него забыл

Чего мучаетесь? Хэш-функцию можно самому придумать в зависимости от задачи. Типа сумма битов, или младшие биты выделить. В зависимости от конкретного значения M и N.

Здравствуйте, VEAPUK, Вы писали:

VEA>Здравствуйте, IROV.., Вы писали:

VEA>Специально для Dufrenite.

IRO>>

IRO>>for( n in N ):
IRO>> if ++M[n] == 2:
IRO>>  return n
IRO>>

VEA>Сколько стоит операция (n in N)?
это цыкл перебор всех элементов N

Здравствуйте, IROV.., Вы писали:

IRO>Здравствуйте, VEAPUK, Вы писали:

VEA>>Здравствуйте, IROV.., Вы писали:

VEA>>Специально для Dufrenite.

IRO>>>

IRO>>>for( n in N ):
IRO>>> if ++M[n] == 2:
IRO>>>  return n
IRO>>>

VEA>>Сколько стоит операция (n in N)?
IRO>это цыкл перебор всех элементов N

Не узнал for each

А если какое-либо число встречается более 2-х раз?

Здравствуйте, _FRED_, Вы писали:

_FR>Здравствуйте, Xobotik, Вы писали:

_FR>>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.

X>>Только больно медленный этот метод.

_FR>Какой именно? Это так же один проход по массиву.

Я просто вас не правильно понял. Просто при реализации данного метода я инициализировал массив суммы диапазона, потом додумался до этого:

        public Int64 GetDuplicateNumber6(int[] array)
        {
            return array.Sum() - array.Distinct().Sum();
        }

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

Здравствуйте, Аноним, Вы писали:

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

Задача дана точно.

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>Для обхода проблемы с O(M) инициализацией можно посмотреть в сторону http://research.swtch.com/2008/03/using-uninitialized-memory-for-fun-and.html

A>Да, круто!
A>Но для обсуждаемой задачки при больших M (например, 2^64) этот подход будет неприменим из-за необходимости аллоцировать O(M) памяти (пусть и грязной) под массив sparse.
Да уже писал.. Хэш фукцию сделайте.. Например, по модулю N. Можно просто по модулю ближайшего большего числа степени 2. Что б не делить, а использовать логическую операцию И.

Здравствуйте, Xobotik, Вы писали:

_FR>>>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.

X>>>Только больно медленный этот метод.
_FR>>Какой именно? Это так же один проход по массиву.

X>Я просто вас не правильно понял. Просто при реализации данного метода я инициализировал массив суммы диапазона, потом додумался до этого:

X>        public Int64 GetDuplicateNumber6(int[] array)
X>        {
X>            return array.Sum() - array.Distinct().Sum();
X>        }

X>Правда от переполнения не застрахованы, но можно как то наверно застраховаться используя частичные суммы.

Посчитай, сколько здесь проходов по массиву и линейная ли сложность. Удивишся

Задача же решается одним лишь вызовом array.Sum() и несколькими математическими операциями, никак не связанными с массивом. Другими словами, то, как в данной задаче вычислить "array.Distinct().Sum()" объяснялось в пятом классе средней школы и я выше даже приводил ссылку на решение.

Здравствуйте, _FRED_, Вы писали:

_FR>Посчитай, сколько здесь проходов по массиву и линейная ли сложность. Удивишся

Здравствуйте, VEAPUK, Вы писали:

VEA>А если какое-либо число встречается более 2-х раз?
Я думаю тут стоит уточнить задание, как мне показалось речь идет о масиве в котором все числа встречаются 1 раз, и только одно два раза.
если же нет

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

тоесть O(N + M) + M памяти.

Здравствуйте, IROV.., Вы писали:

IRO>Здравствуйте, VEAPUK, Вы писали:

VEA>>А если какое-либо число встречается более 2-х раз?
IRO>Я думаю тут стоит уточнить задание, как мне показалось речь идет о масиве в котором все числа встречаются 1 раз, и только одно два раза.
IRO>если же нет

IRO>нужен будет еще один проход по M для того что бы найти число которое встречается именно 2 раза.

IRO>тоесть O(N + M) + M памяти.

IRO>

Ну а зачем уточнять, если точно написано, что дан массив из целых чисел, принимающих значений от 1 до М и один повтор. Подчеркиваю связку "...целых чисел, принимающих значения"

Здравствуйте, Xobotik, Вы писали:

X>Да задачу (стартовую) решили уже без применения каких-то сложных структур:

X>

X>        private static int foo(int[] a)
X>        {
X>            int[] b = new int[a.Length];
X>            for (int i = 0; i < a.Length; i++)
X>            {
X>                if (b[a[i]] == 0)
X>                {
X>                    b[a[i]] = a[i];
X>                }
X>                else
X>                {
X>                    return a[i];
X>                }
X>            }
X>            return 0;
X>        }
X>

X>Теперь просто пытаемся найти еще другие методы решения задачи.

Попробуем мысленно прогнать на последовательности {3,3}. Получим "index out of bounds".

Здравствуйте, Xobotik, Вы писали:

X>Здравствуйте, IROV.., Вы писали:

IRO>>Здравствуйте, VEAPUK, Вы писали:

VEA>>>А если какое-либо число встречается более 2-х раз?
IRO>>Я думаю тут стоит уточнить задание, как мне показалось речь идет о масиве в котором все числа встречаются 1 раз, и только одно два раза.
IRO>>если же нет

IRO>>нужен будет еще один проход по M для того что бы найти число которое встречается именно 2 раза.

IRO>>тоесть O(N + M) + M памяти.

IRO>>

X>Ну а зачем уточнять, если точно написано, что дан массив из целых чисел, принимающих значений от 1 до М и один повтор. Подчеркиваю связку "...целых чисел, принимающих значения"

1 вариант, когда количество чисел N = M + 1 — [1,2,3,4,5,5]
2 вариант, когда количество чисел N <= M + 1 — [1,3,5,5]
3 вариант, когда количество чисел N != M [1,1,1,2,2,2,3,3,3,4,4,4,5,5]

и __ВСЕ__ эти варианты удовлетворяют условию.

	От:	andy1618
	Дата:	10.04.10 06:40
	Оценка:	+1

	От:	Аноним
	Дата:	10.04.10 08:57
	Оценка:

	От:	IROV..
	Дата:	10.04.10 10:27
	Оценка:

	От:	IROV..
	Дата:	10.04.10 10:31
	Оценка:	+1

	От:	VEAPUK
	Дата:	10.04.10 10:57
	Оценка:

От:	_FRED_	@ViIvanov
Дата:	13.04.10 19:51
Оценка:

	От:	batu
	Дата:	11.04.10 07:11
	Оценка:

	От:	Xobotik
	Дата:	14.04.10 19:55
	Оценка:

	От:	Xobotik
	Дата:	20.04.10 17:33
	Оценка:

	От:	OlegMax
	Дата:	26.04.10 15:09
	Оценка: