Здравствуйте, elmal, Вы писали:
E>Конечно есть решение и без HashSet, именно оно и ожидается скорее всего (где то я в этюдах решение видел, насколько я понимаю, основная идея тогда — построить такую контрольную сумму, чтобы можно было вычислить дубликат), но сходу я б ее не решил быстро, как и не ожидал бы такого решения от кандидата.
Судя по всему речь о другой задаче, в которой все числа кроме одного встречаются четное число раз.
E>PS Пока писал — вспомнил решение . А топикстартуру — пусть гуглит, где то здесь проскакивало, наводку я дал
Не надо ничего гуглить. Надо немного сосредоточиться, знаний достаточно. Дорюхать самому гораздо полезнее, чем нагуглить. Прорастут кое-какие нейронные связи в голове, потом ими можно будет пользоваться.
Здравствуйте, Xobotik, Вы писали:
X>>>Есть ли какие-либо другие пути решения задачи? E>>Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
X>А это не O(N^2)?
В C# это называется Dictionary<T>. Если правильно указать ёмкость словарика при инициализации (M), то алгоритм будет работать за время O(N). Но есть один нюанс — отожрётся памяти O(M), что в подобных задачах обычно считается неприемлемым (ибо тогда это эквивалентно заведению простого вспомогательного массива из M элементов, после чего задача становится тривиальной).
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Ну то есть получается надо решить задачу используя только один цикл.
S>Не совсем верно. O(N) допускает кол-во операций, пропорциональное N. Т.е. это может быть один цикл по N, два цикла по N, три и более, но главное чтобы число циклов не зависело от N и чтобы циклы не были вложенными. S>На самом деле вложенные тоже можно, но число итераций вложенных циклов не должно зависеть от N.
S>примеры, удовлетворяющие оценке O(N): S>
S>for(int i = 0; i < N-1; i++)
S>{
S> ...
S>}
S>for(int k = N-1; k >=0; k--)
S>{
S> ...
S>}
S>
S>
S>for(int i = 0; i < N-1; i++)
S>{
S> for(int k = 0; k < 100; k++)
S> {
S> ...
S> }
S>}
S>
S>Это об оценке кол-ва операций O(N). S>А возвращаясь к задаче — да, эта задача решается с помощью одного цикла.
Не понимаю как одним циклом можно сделать. Ну на примере в логике понимаю как нужно сравнивать
Дан массив 1,2,3,4,5
Первая итерация сравниваем следующие комбинации цифр:
1=2;1=3;1=4;1=5.
Следующая итерация:
2=3;2=4;2=5. Мы не сравниваем 2=1 потому что сравнивали эту комбинацию в предыдущей итерации
Следующая итерация:
3=4;3=5.
4=5. последняя итерация
Подход хотя бы такой нужен или логика схожа правильного пути решения?
Здравствуйте, samius, Вы писали:
S>Судя по всему речь о другой задаче, в которой все числа кроме одного встречаются четное число раз.
Принцип тот же самый, там только решение более очевидно, да и тут неглубоко зарыто. Эх... было время, когда такие задачи сходу, и ни про какие хешсеты и не подумал бы, так как не знал о них .
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Ну то есть получается надо решить задачу используя только один цикл.
S>Не совсем верно. O(N) допускает кол-во операций, пропорциональное N. Т.е. это может быть один цикл по N, два цикла по N, три и более, но главное чтобы число циклов не зависело от N и чтобы циклы не были вложенными. S>На самом деле вложенные тоже можно, но число итераций вложенных циклов не должно зависеть от N.
S>примеры, удовлетворяющие оценке O(N): S>
S>for(int i = 0; i < N-1; i++)
S>{
S> ...
S>}
S>for(int k = N-1; k >=0; k--)
S>{
S> ...
S>}
S>
S>
S>for(int i = 0; i < N-1; i++)
S>{
S> for(int k = 0; k < 100; k++)
S> {
S> ...
S> }
S>}
S>
S>Это об оценке кол-ва операций O(N). S>А возвращаясь к задаче — да, эта задача решается с помощью одного цикла.
private static int fff(int[] a)
{
int buf = 0;
int n = 1;
start:
for (int i = 0, j = n ; j <= a.Length - 1; i++, j++)
{
if (a[i] == a[j])
{
buf = a[i];
return buf;
}
}
if (buf == 0)
{
n++;
goto start;
}
return buf;
}
X> private static int fff(int[] a)
X> {
X> int buf = 0;
X> int n = 1;
X> start:
X> for (int i = 0, j = n ; j <= a.Length - 1; i++, j++)
X> {
X> if (a[i] == a[j])
X> {
X> buf = a[i];
X> return buf;
X> }
X> }
X> if (buf == 0)
X> {
X> n++;
X> goto start;
X> }
X> return buf;
X> }
X>
X>Если это неверно, то я не знаю как еще.
Это то же самое сравнение каждого элемента с каждым. Сложность квадратичная O(N^2). Хоть цикл и один, но с помощью goto он прокручивается в худшем случае N-1 раз.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>
X>> private static int fff(int[] a)
X>> {
X>> int buf = 0;
X>> int n = 1;
X>> start:
X>> for (int i = 0, j = n ; j <= a.Length - 1; i++, j++)
X>> {
X>> if (a[i] == a[j])
X>> {
X>> buf = a[i];
X>> return buf;
X>> }
X>> }
X>> if (buf == 0)
X>> {
X>> n++;
X>> goto start;
X>> }
X>> return buf;
X>> }
X>>
X>>Если это неверно, то я не знаю как еще.
S>Это то же самое сравнение каждого элемента с каждым. Сложность квадратичная O(N^2). Хоть цикл и один, но с помощью goto он прокручивается в худшем случае N-1 раз.
Ну это алгоритм не сравнивает 2=1 , когда сравнили 1=2:
Без goto:
private static int fff(int[] a)
{
int buf = 0;
for (int n = 1; n <= a.Length - 1; n++)
{
for (int i = 0, j = n; j <= a.Length - 1; i++, j++)
{
if (a[i] == a[j])
{
buf = a[i];
return buf;
}
}
}
return buf;
}
А как можно без сравнения каждого элемента с каждым я не понимаю.
Здравствуйте, Xobotik, Вы писали:
X>А как можно без сравнения каждого элемента с каждым я не понимаю.
Задача заключается не в том чтобы сравнить каждый с каждым, а в том чтобы понять встречался ли уже такой элемент при просмотре массива или нет. Для этого пройденные элементы надо запоминать где-то вовне массива, чтобы без перебора можно было ответить встречали ли мы элемент K уже или нет.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>А как можно без сравнения каждого элемента с каждым я не понимаю.
S>Задача заключается не в том чтобы сравнить каждый с каждым, а в том чтобы понять встречался ли уже такой элемент при просмотре массива или нет. Для этого пройденные элементы надо запоминать где-то вовне массива, чтобы без перебора можно было ответить встречали ли мы элемент K уже или нет.
Ну а как мы определим встречался элемент или нет без сравнения? Понятно, что с начало запоминаем первый элемент сравниваем с последующими до конца, запоминаем до предпоследнего элемента.
Здравствуйте, Xobotik, Вы писали:
X>Ну а как мы определим встречался элемент или нет без сравнения? Понятно, что с начало запоминаем первый элемент сравниваем с последующими до конца, запоминаем до предпоследнего элемента.
Без сравнения не определить. Но сравнивать каждый с каждым не нужно. В этом ключ.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>А как можно без сравнения каждого элемента с каждым я не понимаю.
S>Задача заключается не в том чтобы сравнить каждый с каждым, а в том чтобы понять встречался ли уже такой элемент при просмотре массива или нет. Для этого пройденные элементы надо запоминать где-то вовне массива, чтобы без перебора можно было ответить встречали ли мы элемент K уже или нет.
То есть мы проходим от первого до последнего элемента. Текущий элемент, добавляем в вспомогательный массив с проверкой нет ли такого же элемента в массиве, если есть то вернем добавляемый элемент. Вот так?
Здравствуйте, Xobotik, Вы писали:
X>То есть мы проходим от первого до последнего элемента. Текущий элемент, добавляем в вспомогательный массив с проверкой нет ли такого же элемента в массиве, если есть то вернем добавляемый элемент. Вот так?
Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Ну а как мы определим встречался элемент или нет без сравнения? Понятно, что с начало запоминаем первый элемент сравниваем с последующими до конца, запоминаем до предпоследнего элемента.
S>Без сравнения не определить. Но сравнивать каждый с каждым не нужно. В этом ключ.
Блин не алгоритм же не сравнивает каждый с каждым:
Он сравнивает точно так:
Так чем же лучше добавление с проверкой нет ли такого же.
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, samius, Вы писали:
S>>Без сравнения не определить. Но сравнивать каждый с каждым не нужно. В этом ключ.
X>Блин не алгоритм же не сравнивает каждый с каждым:
X>Он сравнивает точно так: X>
Это и называется каждый с каждым.
X>Так чем же лучше добавление с проверкой нет ли такого же.
Числом шагов алгоритма, если организовать правильную проверку.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>То есть мы проходим от первого до последнего элемента. Текущий элемент, добавляем в вспомогательный массив с проверкой нет ли такого же элемента в массиве, если есть то вернем добавляемый элемент. Вот так?
S>Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
Я честное слово не знаю как без поиска перебором, да и вообще без поиска, можно каким-либо другим поиском бинарным например, но при этом сортировать массив, но это уже точно не O(N)
Здравствуйте, Xobotik, Вы писали:
S>>Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
X>Я честное слово не знаю как без поиска перебором, да и вообще без поиска, можно каким-либо другим поиском бинарным например, но при этом сортировать массив, но это уже точно не O(N)
Переформулирую исходную задачу:
Дан массив размера N из целых чисел, принимающих значения от 1 до M. Для каждого числа в массиве найти число его повторений в массиве за O(N) операций.
Здравствуйте, samius, Вы писали:
S>Переформулирую исходную задачу: S>Дан массив размера N из целых чисел, принимающих значения от 1 до M. Для каждого числа в массиве найти число его повторений в массиве за O(N) операций.
S>Если эту решишь, с исходной справишься.
private static int ffff(int[] a)
{
Array.Sort(a); // O(n log n)int buf = 0;
for (int i = 0; i <= a.Length - 1; i++) // O(n)
{
if(Array.BinarySearch(b,a[i]) == -1) // O(log n)
{
continue;
}
else
{
return a[i];
}
}
return buf;
}
По поводу той задачи.
Это наверно получше будет, чем сравнение каждый с каждым. Сейчас попытаюсь решить с количеством повторений.
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, samius, Вы писали:
S>>Переформулирую исходную задачу: S>>Дан массив размера N из целых чисел, принимающих значения от 1 до M. Для каждого числа в массиве найти число его повторений в массиве за O(N) операций.
S>>Если эту решишь, с исходной справишься.
X>
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Здравствуйте, samius, Вы писали:
S>>>Переформулирую исходную задачу: S>>>Дан массив размера N из целых чисел, принимающих значения от 1 до M. Для каждого числа в массиве найти число его повторений в массиве за O(N) операций.
S>>>Если эту решишь, с исходной справишься.
X>>
X>>По поводу той задачи. X>>Это наверно получше будет, чем сравнение каждый с каждым.
S>Похуже. BinarySearch работает только с упорядоченными массивами.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Здравствуйте, samius, Вы писали:
S>>>Переформулирую исходную задачу: S>>>Дан массив размера N из целых чисел, принимающих значения от 1 до M. Для каждого числа в массиве найти число его повторений в массиве за O(N) операций.
S>>>Если эту решишь, с исходной справишься.
X>>
X>>По поводу той задачи. X>>Это наверно получше будет, чем сравнение каждый с каждым.
S>Похуже. BinarySearch работает только с упорядоченными массивами.
Огромное спасибо за помощь. Еще один вопрос, не знаю достаточно хорошо правила форума и договоренности между пользователями этого форума, как ставить оценки — то в качестве благодарности поставить за все сообщения в этой ветке тройки или не надо?
. А топикстартуру — пусть гуглит, где то здесь проскакивало, наводку я дал 
