Условие задачи:
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).
Реализация:
private static string separator = ";";
static void Main(string[] args)
{
int[] result = GetIntArray(InputArray());
PrintArray(result);
Console.WriteLine(ff(result));
Console.ReadLine();
}
private static string InputArray()
{
Console.WriteLine("Введите массив, содержащий только целые числа.");
Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
Console.WriteLine("Введите массив: ");
return Console.In.ReadLine();
}
private static int[] GetIntArray(string insert)
{
string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
string[] bufResult = Regex.Split(insert, pattern);
int[] result = new int[bufResult.Length];
for (int i = 0; i < bufResult.Length; i++)
{
result[i] = Int32.Parse(bufResult[i]);
}
return result;
}
private static void PrintArray(int[] array)
{
foreach(int i in array)
{
Console.WriteLine(i);
}
}
private static int ff(int[] array)
{
int m = 1;
int buf = 0;
// общее количество сравнений (n-1)^2, где n - длина массиваfor (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
{
// количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)for (int j = 1; j < array.Length; j++)
{
if (array[0] == array[j])
{
buf = array[0];
goto result;
}
}
Swap(array, m);
m++;
}
result:
return buf;
}
private static void Swap(int[] array, int index)
{
int temp = array[index];
array[index] = array[0];
array[0] = temp;
}
Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
for (int j = 1; j < array.Length - 1; j++)
при этом работа цикла
for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Xobotik, Вы писали:
X>>Найти это число за время O(N).
X>> // общее количество сравнений (n-1)^2, где n — длина массива
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>блин точно) а есть ли какой-нибудь другой подход не по такой логике.
S>Есть. S>А самому не интересно найти?
Можете сказать хоть куда копать? Голова забита только этим методом.
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Здравствуйте, Xobotik, Вы писали:
X>>>Найти это число за время O(N).
X>>> // общее количество сравнений (n-1)^2, где n — длина массива
X>А разве O((n-1)^2) ~ O(n)?
Здравствуйте, Xobotik, Вы писали:
X>Есть ли какие-либо другие пути решения задачи?
Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>Можете сказать хоть куда копать? Голова забита только этим методом.
S>Нужно копать в сторону удовлетворения требования O(N)
S>Если скажу больше, то будет неинтересно
private static int fff(int[] array)
{
int buf = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] == array[i+1])
{
continue;
}
else
{
buf = array[i];
return buf;
}
}
return buf;
}
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
X>Реализация: X>
X>private static string separator = ";";
X> static void Main(string[] args)
X> {
X> int[] result = GetIntArray(InputArray());
X> PrintArray(result);
X> Console.WriteLine(ff(result));
X> Console.ReadLine();
X> }
X> private static string InputArray()
X> {
X> Console.WriteLine("Введите массив, содержащий только целые числа.");
X> Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
X> Console.WriteLine("Введите массив: ");
X> return Console.In.ReadLine();
X> }
X> private static int[] GetIntArray(string insert)
X> {
X> string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
X> string[] bufResult = Regex.Split(insert, pattern);
X> int[] result = new int[bufResult.Length];
X> for (int i = 0; i < bufResult.Length; i++)
X> {
X> result[i] = Int32.Parse(bufResult[i]);
X> }
X> return result;
X> }
X> private static void PrintArray(int[] array)
X> {
X> foreach(int i in array)
X> {
X> Console.WriteLine(i);
X> }
X> }
X> private static int ff(int[] array)
X> {
X> int m = 1;
X> int buf = 0;
X> // общее количество сравнений (n-1)^2, где n - длина массива
X> for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X> {
X> // количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)
X> for (int j = 1; j < array.Length; j++)
X> {
X> if (array[0] == array[j])
X> {
X> buf = array[0];
X> goto result;
X> }
X> }
X> Swap(array, m);
X> m++;
X> }
X> result:
X> return buf;
X> }
X> private static void Swap(int[] array, int index)
X> {
X> int temp = array[index];
X> array[index] = array[0];
X> array[0] = temp;
X> }
X>
X>Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
X>
X>for (int j = 1; j < array.Length - 1; j++)
X>
X>при этом работа цикла
X>
X>for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X>
X>не прерывается
X>Заранее спасибо!
private static int fff(int[] array)
{
int buf = 0;
for (int i = 0; i < array.Length; i++)
{
if (array[i] == array[i+1])
{
continue;
}
else
{
buf = array[i];
return buf;
}
}
return buf;
}
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, Xobotik, Вы писали:
X>>Есть ли какие-либо другие пути решения задачи? E>Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
X> private static int fff(int[] array)
X> {
X> int buf = 0;
X> for (int i = 0; i < array.Length; i++)
X> {
X> if (array[i] == array[i+1])
X> {
X> continue;
X> }
X> else
X> {
X> buf = array[i];
X> return buf;
X> }
X> }
X> return buf;
X> }
X>
X>Удовлетворяет условию O(N)?
Удовлетворяет O(N) но не решает задачу. Вернет первый элемент массива, который не дублируется следующим элементом массива. До конца массива не дойдет, вылетит по IndexOutOfRangeException.
Здравствуйте, elmal, Вы писали:
E>Эээ, а что, итерация по массиву, занесение результата в HashSet (не знаю как аналог в .NET называется) и выход, если результат уже заносили — не прокатит за решение? Обязательно извращаться?
Полагаю, что автор задачи вряд ли рассчитывал увидеть в решении задачи по теме массивов HashSet.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>
X>> private static int fff(int[] array)
X>> {
X>> int buf = 0;
X>> for (int i = 0; i < array.Length; i++)
X>> {
X>> if (array[i] == array[i+1])
X>> {
X>> continue;
X>> }
X>> else
X>> {
X>> buf = array[i];
X>> return buf;
X>> }
X>> }
X>> return buf;
X>> }
X>>
X>>Удовлетворяет условию O(N)?
S>Удовлетворяет O(N) но не решает задачу. Вернет первый элемент массива, который не дублируется следующим элементом массива. До конца массива не дойдет, вылетит по IndexOutOfRangeException.
Ну то есть получается надо решить задачу используя только один цикл.
Здравствуйте, Xobotik, Вы писали:
X>Ну то есть получается надо решить задачу используя только один цикл.
Не совсем верно. O(N) допускает кол-во операций, пропорциональное N. Т.е. это может быть один цикл по N, два цикла по N, три и более, но главное чтобы число циклов не зависело от N и чтобы циклы не были вложенными.
На самом деле вложенные тоже можно, но число итераций вложенных циклов не должно зависеть от N.
примеры, удовлетворяющие оценке O(N):
for(int i = 0; i < N-1; i++)
{
...
}
for(int k = N-1; k >=0; k--)
{
...
}
for(int i = 0; i < N-1; i++)
{
for(int k = 0; k < 100; k++)
{
...
}
}
Это об оценке кол-ва операций O(N).
А возвращаясь к задаче — да, эта задача решается с помощью одного цикла.
Здравствуйте, samius, Вы писали:
S>Полагаю, что автор задачи вряд ли рассчитывал увидеть в решении задачи по теме массивов HashSet.
Лично я бы, если бы дал такую задачу, именно такое решение бы и ожидал увидеть. Так как такие задачи довольно часты на практике, и по крайней мере я их всегда через HashSet делаю. Конечно есть решение и без HashSet, именно оно и ожидается скорее всего (где то я в этюдах решение видел, насколько я понимаю, основная идея тогда — построить такую контрольную сумму, чтобы можно было вычислить дубликат), но сходу я б ее не решил быстро, как и не ожидал бы такого решения от кандидата. Да и не очень будет это решение, при всей своей мегаоптимальности и красивости универсальным, ни разу у меня не было случая, когда постановка задачи была именно такая (именно 2 раза встречается, и именно от 1 до М).
PS Пока писал — вспомнил решение . А топикстартуру — пусть гуглит, где то здесь проскакивало, наводку я дал
Здравствуйте, 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 работает только с упорядоченными массивами.
Огромное спасибо за помощь. Еще один вопрос, не знаю достаточно хорошо правила форума и договоренности между пользователями этого форума, как ставить оценки — то в качестве благодарности поставить за все сообщения в этой ветке тройки или не надо?
Здравствуйте, Xobotik, Вы писали:
X>Огромное спасибо за помощь. Еще один вопрос, не знаю достаточно хорошо правила форума и договоренности между пользователями этого форума, как ставить оценки — то в качестве благодарности поставить за все сообщения в этой ветке тройки или не надо?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
X>>То есть мы проходим от первого до последнего элемента. Текущий элемент, добавляем в вспомогательный массив с проверкой нет ли такого же элемента в массиве, если есть то вернем добавляемый элемент. Вот так?
S>Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
Сделал. Метод под номером 4.
// Метод №1.private static int f(int[] array)
{
int m = 1;
int buf = 0;
// количество сравнений (n-1)^2, где n - длина массиваfor (int i = 0; i <= (array.Length - 1) * (array.Length - 1); i++)
{
// количество перестановок (n-1), где n - длина массиваfor (int j = 1; j < array.Length; j++)
{
if (array[0] == array[j])
{
buf = array[0];
return buf;
}
}
int temp = array[m];
array[m] = array[0];
array[0] = temp;
m++;
}
return buf;
}
// Метод №2.private static int ff(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;
}
// Метод №3.private static int fff(int[] a)
{
Array.Sort(a);
int buf = 0;
for (int i = 0; i <= a.Length - 1; i++)
{
if(Array.BinarySearch(a,a[i]) == -1)
{
continue;
}
else
{
buf = a[i];
return buf;
}
}
return buf;
}
// Метод №4.private static int ffff(int[] a)
{
int buf = 0;
int[] b = new int[a.Length - 1];
b[0] = a[0];
int n = 0;
for (int i = 1; i <= a.Length - 1; i++)
{
if (b.Contains(a[i]))
{
buf = a[i];
return buf;
}
else
{
n++;
b[n] = a[i];
}
}
return buf;
}
Вот четвертый метод со вспомогательным массивов и без поиска перебором (наверно здесь имелось ввиду без линейного поиска). LINQ — выручил однако. Но по производительности для 7 элементов 4-ый метод наихудший.
Рассматривал вот такие массивы:
int[] a = new int[] { 1, 2, 3, 4, 5, 1, 8 };
int[] b = new int[] { 3, 1, 2, 4, 1, 6, 8 };
int[] c = new int[] { 3, 2, 1, 1, 5, 6, 8 };
int[] d = new int[] { 1, 2, 3, 4, 1, 6, 8 };
int[] e = new int[] { 3, 2, 5, 4, 1, 1, 8 };
int[] f = new int[] { 3, 2, 1, 4, 6, 1, 8 };
int[] j = new int[] { 3, 2, 1, 4, 6, 8, 1 };
Общий рейтинг:
1) Метод №2;
2) Метод №1;
3) Метод №3;
4) Метод №4.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
S>>>Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
X>>Сделал. Метод под номером 4.
S>4-ый метод хоть сам не перебирает элементы вспомогательного массива, зато это делает LINQ в методе Contains. Сложность этого решения квадратичная.
S>Мой вариант задачи не делал, где нужно посчитать кол-ва упоминаний элементов массива?
Нет еще не делал, но мысли есть по поводу этой задачки.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Массив для анализа AA
резервируем массив Ar длиной M с нулями
For I=0 To N-1
IF AR[AA[I]] <> 0 Then EXIT С НАЙДЕНЫМ ЗНАЧЕНИЕМ
Else AR[AA[I]]+=1
end For
В среднем O(3N/2) что явно лучше чем O(N)
Если M велико можно по разрядам в байте фиксировать факт наличия данного значения.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Xobotik, Вы писали:
S>>>Близко, но нужно избавиться от поиска перебором во вспомогательном массиве.
X>>Сделал. Метод под номером 4.
S>4-ый метод хоть сам не перебирает элементы вспомогательного массива, зато это делает LINQ в методе Contains. Сложность этого решения квадратичная.
S>Мой вариант задачи не делал, где нужно посчитать кол-ва упоминаний элементов массива?
Решил все таки:
P.S. на комментарий batu не смотрел
private static int foo(int[] a)
{
int buf = 0;
int[] b = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
if (b[a[i]] == 0)
{
b[a[i]] = a[i];
}
else
{
buf = a[i];
return buf;
}
}
return buf;
}
Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, batu, Вы писали:
B>>В среднем O(3N/2) что явно лучше чем O(N)
DR>Несколько замечаний:
DR>1. 3N/2 > N DR>2. O(3N/2) = O(N) DR>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.
Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N). Может быть в задаче, то и имелось ввиду за O(M).
Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, batu, Вы писали:
B>>В среднем O(3N/2) что явно лучше чем O(N)
DR>Несколько замечаний:
DR>1. 3N/2 > N DR>2. O(3N/2) = O(N) DR>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.
Согласен. Я не правильно записал Я имел ввиду, что алгоритм в среднем требует половины цикла. Как-то надо было разделить пополамПотому имелось в виду значение O как фиксированое значение для обработки одного тела цикла, в общем случае именно это подразумевается как коэффициент. Это тот случай когда и ты прав и я прав
А сложность таки N. Цикл по N. M может затребовать памяти если будет велико.
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, Don Reba, Вы писали:
DR>>Здравствуйте, batu, Вы писали:
B>>>В среднем O(3N/2) что явно лучше чем O(N)
DR>>Несколько замечаний:
DR>>1. 3N/2 > N DR>>2. O(3N/2) = O(N) DR>>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.
X>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N). Может быть в задаче, то и имелось ввиду за O(M).
Видимо алгоритм не понят.
Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа. Понятное дело что перед выбором следующего числа анализируемого массива, мы проверяем не было ли единицы по данному индексу, если есть, то это число уже встречалось. Можно выходить из цикла. Поставленая задача решена. Без сравнения никак нельзя. Что-то по любому надо проверять. А перебора вспомогательного массива нет. Так что я не пойму откуда возникла сложность O(M). В среднем достаточно половины циклов массива размером N для нахожения повторяющегося числа.
B>Видимо алгоритм не понят. B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа. Понятное дело что перед выбором следующего числа анализируемого массива, мы проверяем не было ли единицы по данному индексу, если есть, то это число уже встречалось. Можно выходить из цикла. Поставленая задача решена. Без сравнения никак нельзя. Что-то по любому надо проверять. А перебора вспомогательного массива нет. Так что я не пойму откуда возникла сложность O(M). В среднем достаточно половины циклов массива размером N для нахожения повторяющегося числа.
тебе нужно проинициализировать нулями массив размером M. Формально это O(M), если забыть о трюках с paged memory management
Здравствуйте, Xobotik, Вы писали:
X>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N).
Лучше всего — HashSet. Удовлетворяет условию полностью.
X>Может быть в задаче, то и имелось ввиду за O(M).
А может все числа встречаются по два раза, а одно число только один раз?
А может массив содержит все числа от 1 до M и плюс еще одно повторение, т.е. длина массива равна M+1?
С учетом таких вариантов задача будет занимательной
А так... Ну возьмем M = 2^64. Из работающих алгоритмов остаются только хэши да деревья.
Можно использовать готовые, можно сделать самому. Может это и требуется?
Здравствуйте, batu, Вы писали:
B>Здравствуйте, Xobotik, Вы писали:
X>>Здравствуйте, Don Reba, Вы писали:
DR>>>Здравствуйте, batu, Вы писали:
B>>>>В среднем O(3N/2) что явно лучше чем O(N)
DR>>>Несколько замечаний:
DR>>>1. 3N/2 > N DR>>>2. O(3N/2) = O(N) DR>>>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.
X>>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N). Может быть в задаче, то и имелось ввиду за O(M). B>Видимо алгоритм не понят. B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа. Понятное дело что перед выбором следующего числа анализируемого массива, мы проверяем не было ли единицы по данному индексу, если есть, то это число уже встречалось. Можно выходить из цикла. Поставленая задача решена. Без сравнения никак нельзя. Что-то по любому надо проверять. А перебора вспомогательного массива нет. Так что я не пойму откуда возникла сложность O(M). В среднем достаточно половины циклов массива размером N для нахожения повторяющегося числа.
Да все я понял, под сравнениями я имел ввиду >, <, <=, >=. Я просто решил задачу в пятницу, захожу сюда, чтобы отписаться вчера, а тут вы решение уже сказали, обидно блин. Такое ощущение, что не сам догадался.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N).
Б>Лучше всего — HashSet. Удовлетворяет условию полностью.
X>>Может быть в задаче, то и имелось ввиду за O(M).
Б>А может все числа встречаются по два раза, а одно число только один раз? Б>А может массив содержит все числа от 1 до M и плюс еще одно повторение, т.е. длина массива равна M+1? Б>С учетом таких вариантов задача будет занимательной
Задача поставлена четко в начале темы, никаких там если бы, да как бы нет
Б>А так... Ну возьмем M = 2^64. Из работающих алгоритмов остаются только хэши да деревья. Б>Можно использовать готовые, можно сделать самому. Может это и требуется?
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N).
Б>Лучше всего — HashSet. Удовлетворяет условию полностью.
X>>Может быть в задаче, то и имелось ввиду за O(M).
Б>А может все числа встречаются по два раза, а одно число только один раз? Б>А может массив содержит все числа от 1 до M и плюс еще одно повторение, т.е. длина массива равна M+1? Б>С учетом таких вариантов задача будет занимательной
На счет занимательности, небольшое еще добавление, за время O(log n) сделать)
Б>А так... Ну возьмем M = 2^64. Из работающих алгоритмов остаются только хэши да деревья. Б>Можно использовать готовые, можно сделать самому. Может это и требуется?
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>На счет занимательности, небольшое еще добавление, за время O(log n) сделать)
Б>Лучше, чем за O(n) не сделать — массив необходимо просмотреть как минимум один раз.
Здравствуйте, andy1618, Вы писали:
A>В C# это называется Dictionary<T>. Если правильно указать ёмкость словарика при инициализации (M), то алгоритм будет работать за время O(N). Но есть один нюанс — отожрётся памяти O(M), что в подобных задачах обычно считается неприемлемым (ибо тогда это эквивалентно заведению простого вспомогательного массива из M элементов, после чего задача становится тривиальной).
Упс, ошибся! Ведь M может быть очень велико и существенно превышать N (например, M=2^64, N=1000), а для шустрой работы хешированного словарика вполне достаточно памяти порядка O(N).
Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
A>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм.
Чтобы сохранить O(1) (в среднем) доступ нужен хэш размером N*lgN, опять таки вылазит логарифм.
X>Да все я понял, под сравнениями я имел ввиду >, <, <=, >=. Я просто решил задачу в пятницу, захожу сюда, чтобы отписаться вчера, а тут вы решение уже сказали, обидно блин. Такое ощущение, что не сам догадался.
Та ладно.. Фигня все это. Развлекаемся.
Здравствуйте, dilmah, Вы писали:
D>тебе нужно проинициализировать нулями массив размером M. Формально это O(M), если забыть о трюках с paged memory management
Формально да. Есть языки, которые не требуют инициализации.. А так ты прав
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Странно, что никто не предложил такой вариант: lexical sort (=O(N*log(M))) + ещё один проход для сравнения соседних элементов (=O(N)).
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, Xobotik, Вы писали:
F>Странно, что никто не предложил такой вариант: lexical sort (=O(N*log(M))) + ещё один проход для сравнения соседних элементов (=O(N)).
Что-то я не понял откуда в lexical sort оценка O(N*log(M))
radix sort для Int32 займет O(4*N). Т.е. формально за O(N) с дополнительной памятью O(C).
S>Что-то я не понял откуда в lexical sort оценка O(N*log(M))
S>radix sort для Int32 займет O(4*N). Т.е. формально за O(N) с дополнительной памятью O(C).
ну вот эта четверка это и есть log(M) -- другими словами -- количество бит в сортируемых числах
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, andy1618, Вы писали:
A>>В C# это называется Dictionary<T>. Если правильно указать ёмкость словарика при инициализации (M), то алгоритм будет работать за время O(N). Но есть один нюанс — отожрётся памяти O(M), что в подобных задачах обычно считается неприемлемым (ибо тогда это эквивалентно заведению простого вспомогательного массива из M элементов, после чего задача становится тривиальной).
A>Упс, ошибся! Ведь M может быть очень велико и существенно превышать N (например, M=2^64, N=1000), а для шустрой работы хешированного словарика вполне достаточно памяти порядка O(N). A>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
Да вы правы Словари решают задачу за O(N)
public int GetDuplicateNumber(int[] array)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
foreach (int i in array) // O(N)
{
if (dictionary.ContainsKey(i)) // Этот метод является операцией порядка сложности O(1)
{
return i;
}
else
{
dictionary.Add(i, 0); // O(1) размер словаря, равен размеру массива, размер не увеличивается
}
}
return 0;
// результат: O(N*1*1) = O(N)
}
Здравствуйте, dilmah, Вы писали:
A>>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
D>не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм. D>Чтобы сохранить O(1) (в среднем) доступ нужен хэш размером N*lgN, опять таки вылазит логарифм.
Я так долго копил баллы, за что -1 то? Я метод делал строго по документации MSDN.
D>>не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм.
DR>Не будет, посчитай. К тому же, хэш можно сделать размером kN для любого положительного k.
ок, согласен, посчитал количество коллизий стремится к распределению пуассона, так что в среднем константный оверхед.
Но все равно, зависимость от M спрятана неявно -- в вычислении хэша.
X> public int GetDuplicateNumber(int[] array)
X> {
X> Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
X> foreach (int i in array) // O(N)
X> {
X> if (dictionary.ContainsKey(i)) // Этот метод является операцией порядка сложности O(1)
X> {
X> return i;
X> }
X> else
X> {
X> dictionary.Add(i, 0); // O(1) размер словаря, равен размеру массива, размер не увеличивается
X> }
X> }
X> return 0;
X> // результат: O(N*1*1) = O(N)
X> }
X>
а вот так:
public int GetDuplicateNumber(int[] array)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
for (int i = 0; i < array.Length; i++)
{
if (dictionary.ContainsKey(array[i]))
{
return array[i];
}
else
{
dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это шаг цикла for
}
}
return 0;
}
D>>Но все равно, зависимость от M спрятана неявно -- в вычислении хэша.
S>Можно развернуть мысль?
ну в исходной задаче было озвучено 2 параметра: N и M.
Решение с хэшом имеет сложность O(N) только в предположении, что M не превышает некого фиксированного числа, скажем UINT64_MAX
Но так как M тоже является параметром, то формально сложность равна O(N*log(M)), потому что чем больше M, тем больше бит в числах.
X> public int GetDuplicateNumber(int[] array)
X> { ...
X> dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это
X> ...
X> }
X>
Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Ведь это:
1. Запутывает код.
2. Увеличивает требования к памяти.
Здравствуйте, Буравчик, Вы писали:
Б>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>
X>> public int GetDuplicateNumber(int[] array)
X>> { ...
X>> dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это
X>> ...
X>> }
X>>
Б>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Б>Ведь это: Б>1. Запутывает код.
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Буравчик, Вы писали:
Б>>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
A>Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Да задачу (стартовую) решили уже без применения каких-то сложных структур:
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Весь топик не читал, боясь встретить подсказки, а связи нейронные наростить надо бы, ибо вчера была кушал водку
Правиьно ли я понимаю, что только указанного условия достаточно для решения? То есть
порядок N и M может быть достаточно большим
в массиве вовсе не обязательно присутствуют все 1..M, и, как следсnвие, неизвестно, что больше — N или M, то есть M может быть 10^9, а массив [1, 2, 3, 2]
только одно число повторяется (обязательно повторяется) и строго два раза
?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Буравчик, Вы писали:
Б>>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
A>Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Да задачу (стартовую) решили уже без применения каких-то сложных структур:
private static int foo(int[] a)
{
int[] b = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
if (b[a[i]] == 0)
{
b[a[i]] = a[i];
}
else
{
return a[i];
}
}
return 0;
}
Теперь просто пытаемся найти еще другие методы решения задачи.
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
_FR>Весь топик не читал, боясь встретить подсказки, а связи нейронные наростить надо бы, ибо вчера была кушал водку
_FR>Правиьно ли я понимаю, что только указанного условия достаточно для решения? То есть _FR>
_FR>порядок N и M может быть достаточно большим _FR>в массиве вовсе не обязательно присутствуют все 1..M, и, как следсnвие, неизвестно, что больше — N или M, то есть M может быть 10^9, а массив [1, 2, 3, 2] _FR>только одно число повторяется (обязательно повторяется) и строго два раза _FR>_FR>?
Здравствуйте, Xobotik, Вы писали:
X>Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Словарь хранит пары (ключ -> значение). Его основная цель — быстро находить "значение" по его "ключу". В данном контейнере поиск пары (ключ -> значение) осуществляется по хэшу "ключа", а хэш "значения" в поиске не участвует. Поэтому на коллизии влияет только хэш ключа.
Нужна другая структура данных, от которой требуется:
— быстро проверять наличие элемента (на основе хэша)
— быстро добавлять новый элемент
Б>>1. Запутывает код. X>Отнюдь.
Запутывает, потому что словарь используется не по назначению.
Б>>2. Увеличивает требования к памяти. X>Увеличивает на парочку бит
Не, так неинтересно: я про большие числа потому и спросил, что бы узнать, можно ли выделять память, пропорциональную N или M.
Есть известная задачка на поиск цикла в однонаправленном списке. Многие задают ей, не говоря об имеющихся ограничениях. А самое простейшее решение в таких случаях — тот же HashSet — запоминание того, что прошли в нём. Всяко быстрее догонялок будет :о))
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Б>Словарь хранит пары (ключ -> значение). Его основная цель — быстро находить "значение" по его "ключу". В данном контейнере поиск пары (ключ -> значение) осуществляется по хэшу "ключа", а хэш "значения" в поиске не участвует. Поэтому на коллизии влияет только хэш ключа.
Точно, перепутал.
Б>Нужна другая структура данных, от которой требуется: Б>- быстро проверять наличие элемента (на основе хэша) Б>- быстро добавлять новый элемент
здесь было предложение использовать фильтр Блума.
Б>>>1. Запутывает код. X>>Отнюдь. Б>Запутывает, потому что словарь используется не по назначению.
Ну извините мы же не решаем задачу о нахождения оптимального стиля программирования, а решаем конкретную постановку. Да и 10 строк мало кого запутают.
Б>>>2. Увеличивает требования к памяти. X>>Увеличивает на парочку бит Б>Можно обойтись и без этого.
ну а вообще объясняю еще раз причину добавления в ключи значений из массива построчно исходя из кода.
public int GetDuplicateNumber(int[] array)
{
Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>(array.Length);
for (int i = 0; i < array.Length; i++)
{
if (dictionary.ContainsKey(array[i])) // операция ContainsKey равна O(1)
{
return array[i];
}
else
{
// операция Add() - O(1) при фиксированном значении размера словаря
dictionary.Add(array[i], 0); // добавляем в ключи значения из массива не найденные методом ContainsKey(). Так как мы ищем методом ContainsKey() не в значения же словаря
//добавлять значения массива
}
}
return 0;
}
На счет ContainsKey(): здесь см. заметки
На счет Add(): здесь см. заметки
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Xobotik, Вы писали:
X>>Да задачу (стартовую) решили уже без применения каких-то сложных структур:
X>>здесь
_FR>Не, так неинтересно: я про большие числа потому и спросил, что бы узнать, можно ли выделять память, пропорциональную N или M.
Ну тут просто постановка задачи всячески искажалась, что я сам запутался Вы правы в любом случае.
_FR>Есть известная задачка на поиск цикла в однонаправленном списке. Многие задают ей, не говоря об имеющихся ограничениях. А самое простейшее решение в таких случаях — тот же HashSet — запоминание того, что прошли в нём. Всяко быстрее догонялок будет :о))
Здравствуйте, Буравчик, Вы писали:
Б>Нужна другая структура данных, от которой требуется: Б>- быстро проверять наличие элемента (на основе хэша) Б>- быстро добавлять новый элемент
Б>>>1. Запутывает код. X>>Отнюдь.
Б>Запутывает, потому что словарь используется не по назначению.
Да, конечно, в терминах C# надо вместо Dictionary использовать свежепоявившийся HashSet, совсем про него забыл
Здравствуйте, _FRED_, Вы писали:
_FR> неизвестно, что больше — N или M
Судя по условию задачи, N ограничено сверху значением M+1, т.к. иначе будет более одного дубликата.
Кстати, если бы было соблюдено равенство N = M + 1 (т.е. присутствовали бы все без исключения числа от 1 до M с одним дубликатом), то задача бы решалась обычным XOR-ом за O(N) без доп. памяти.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Я сомневаюсь, что существует решение лутче чем через хеш (в дотнете — HashSet). Если такое решение существует, то оно должно использовать либо меньше памяти, либо меньшую временную сложность. Само существование такое алгоритма означает, что его можно использовать для стандартного хеша, у которого отсутсвует операция удаления — некий AddOnlyHashSet. А это, согласитесь, довольно таки полезный класс. То есть, если б существовал такой алгоритм — в бибилиотеках был бы специальный класс AddOnlyHashSet.
Здравствуйте, andy1618, Вы писали:
_FR>> неизвестно, что больше — N или M
A>Судя по условию задачи, N ограничено сверху значением M+1, т.к. иначе будет более одного дубликата.
Вовсе не обязательно: в первоначальной формулировке не сказано, что какое-либо числе не может повторяться в массиве три и большее количество раз.
A>Кстати, если бы было соблюдено равенство N = M + 1 (т.е. присутствовали бы все без исключения числа от 1 до M с одним дубликатом), то задача бы решалась обычным XOR-ом за O(N) без доп. памяти.
Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, Pro100Oleh, Вы писали:
PO>некий AddOnlyHashSet. А это, согласитесь, довольно таки полезный класс. То есть, если б существовал такой алгоритм — в бибилиотеках был бы специальный класс AddOnlyHashSet.
Ну, вышеупомянутые фильтры Блума это и есть что типа AddOnlyHashSet
Здравствуйте, _FRED_, Вы писали:
_FR>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
Здравствуйте, Xobotik, Вы писали:
_FR>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
X>Только больно медленный этот метод.
Да ладно, это как раз практически идеальный метод — требуется только один проход с суммированием плюс несколько арифметических действий. Быстрее на стандартных компьютерных архитектурах вряд ли получится!
Но, как написано выше, этот алгоритм относится к частному случаю N=M+1 (т.е. в исходном массиве есть ВСЕ числа от 1 до M плюс какое-то число встречается дважды).
Здравствуйте, Xobotik, Вы писали:
_FR>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
X>Только больно медленный этот метод.
Какой именно? Это так же один проход по массиву.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, -VladK-, Вы писали:
VK>Народ, да вы че? VK>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!
Разве в условии сказано что N = M + 1?
N = 10, M = 1000. Куда приложить прогрессию?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, -VladK-, Вы писали:
VK>>Народ, да вы че? VK>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!
S>Разве в условии сказано что N = M + 1? S>N = 10, M = 1000. Куда приложить прогрессию?
"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.
Да, круто!
Но для обсуждаемой задачки при больших M (например, 2^64) этот подход будет неприменим из-за необходимости аллоцировать O(M) памяти (пусть и грязной) под массив sparse.
Здравствуйте, Аноним, Вы писали:
S>>Разве в условии сказано что N = M + 1? S>>N = 10, M = 1000. Куда приложить прогрессию?
А>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно А>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.
У меня сначала тоже такая мысль была. Но я решил, что тогда бы не стали парить мозги и написали бы, что дан массив из M+1 чисел.
А вообще, интересно, откуда эта задачка взялась: если из института с лабораторной работы — это одно, если с крутой олимпиады по информатике — это другое
Re[5]: Поиск повторяющегося числа в массиве
От:
Аноним
Дата:
10.04.10 08:57
Оценка:
Здравствуйте, 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.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Самое простое выделить второй масив из M элементов
пройтись по по первому масиву N и в масиве M возвести флаг по значению, если флаг есть — то вот и оно
for( n in N ):
if ++M[n] == 2:
return n
а если без памяти порядка M нужно думать, ушел думать
Здравствуйте, 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, хоть и меньше.
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Буравчик, Вы писали:
Б>>Нужна другая структура данных, от которой требуется: Б>>- быстро проверять наличие элемента (на основе хэша) Б>>- быстро добавлять новый элемент
Б>>>>1. Запутывает код. X>>>Отнюдь.
Б>>Запутывает, потому что словарь используется не по назначению.
A>Да, конечно, в терминах C# надо вместо Dictionary использовать свежепоявившийся HashSet, совсем про него забыл
Чего мучаетесь? Хэш-функцию можно самому придумать в зависимости от задачи. Типа сумма битов, или младшие биты выделить. В зависимости от конкретного значения M и N.
Здравствуйте, _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>Правда от переполнения не застрахованы, но можно как то наверно застраховаться используя частичные суммы.
Посчитай, сколько здесь проходов по массиву и линейная ли сложность. Удивишся Задача же решается одним лишь вызовом array.Sum() и несколькими математическими операциями, никак не связанными с массивом. Другими словами, то, как в данной задаче вычислить "array.Distinct().Sum()" объяснялось в пятом классе средней школы и я выше даже приводил ссылку на решение.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, _FRED_, Вы писали:
_FR>Посчитай, сколько здесь проходов по массиву и линейная ли сложность. Удивишся Задача же решается одним лишь вызовом array.Sum() и несколькими математическими операциями, никак не связанными с массивом. Другими словами, то, как в данной задаче вычислить "array.Distinct().Sum()" объяснялось в пятом классе средней школы и я выше даже приводил ссылку на решение.
Да это то понятно, дело в том, что если на входе массив { 1, 500, 600, 1 }, то данный метод недействителен.
Здравствуйте, VEAPUK, Вы писали:
VEA>А если какое-либо число встречается более 2-х раз?
Я думаю тут стоит уточнить задание, как мне показалось речь идет о масиве в котором все числа встречаются 1 раз, и только одно два раза.
если же нет
нужен будет еще один проход по M для того что бы найти число которое встречается именно 2 раза.
Здравствуйте, IROV.., Вы писали:
IRO>Здравствуйте, VEAPUK, Вы писали:
VEA>>А если какое-либо число встречается более 2-х раз? IRO>Я думаю тут стоит уточнить задание, как мне показалось речь идет о масиве в котором все числа встречаются 1 раз, и только одно два раза. IRO>если же нет
IRO>нужен будет еще один проход по M для того что бы найти число которое встречается именно 2 раза.
IRO>тоесть O(N + M) + M памяти.
IRO>
Ну а зачем уточнять, если точно написано, что дан массив из целых чисел, принимающих значений от 1 до М и один повтор. Подчеркиваю связку "...целых чисел, принимающих значения"
Здравствуйте, 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]
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
X>...
X>Есть ли какие-либо другие пути решения задачи?
Классная ссылка! Последний подход (с обнаружением цикла у графа методом "догонялок") красивый, но он не будет работать для той трактовки задачи, когда N < M+1 (например, на упомянутом выше массиве: { 1, 500, 600, 1 } ).
Т.е. пока что все решения для такой трактовки требуют доп. память.
Здравствуйте, IROV.., Вы писали:
IRO>1 вариант, когда количество чисел N = M + 1 — [1,2,3,4,5,5] IRO>2 вариант, когда количество чисел N <= M + 1 — [1,3,5,5]
Это все понятно.
IRO>3 вариант, когда количество чисел N != M [1,1,1,2,2,2,3,3,3,4,4,4,5,5]
Давайте еще раз повторим условие задачи:
Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза. Найти это число за время O(N).
"Найти это число за время O(N)." — говорит нам о том, что в массиве один повтор ищется за время O(N), ну а остальные, если они есть, ищутся тоже за это же самое время (Хотя об этом не слова, что в массиве может быть какое-либо K повторов).
Третий вариант, можно сказать частный случай, который нужно учесть при разработке идеального алгоритма поиска, ну то есть скорее всего очищать буферный массив и удалять повторяющиеся из входного массива, если есть более одного повтора.
P.S. я мог ошибиться в размышлениях, заранее сорри.
X>Заранее спасибо!
баян..
Резервируем массив ar [m] инициируем его нулями
И каждое новое значение аi
Записываем единичку в ar[ai] перед этим проверяя не равно ли оно 1.
Если равно 1 то это значение уже встречалось.
Один цикл по N, да и то не полностью с надеждой что повторяющееся встретится раньше.
fOR I=0 TO N
IF AR[AI]<>1 THEN AR[AI]=1 ELSE EXIT FOR
NEXT I
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
A>Кстати, интересно, а откуда эта задачка?
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Решение тривиально. Заводим массив бит ММ с размером M инициализируя нульями.
Пробегая через массив с размером N усатавливаем соответствующий бит (тоесть n-ный бит, где n текущий элемент из N)
в массиве ММ если неустановлен, иначе текущий элемент искомый.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
X>Реализация: X>
X>private static string separator = ";";
X> static void Main(string[] args)
X> {
X> int[] result = GetIntArray(InputArray());
X> PrintArray(result);
X> Console.WriteLine(ff(result));
X> Console.ReadLine();
X> }
X> private static string InputArray()
X> {
X> Console.WriteLine("Введите массив, содержащий только целые числа.");
X> Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
X> Console.WriteLine("Введите массив: ");
X> return Console.In.ReadLine();
X> }
X> private static int[] GetIntArray(string insert)
X> {
X> string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
X> string[] bufResult = Regex.Split(insert, pattern);
X> int[] result = new int[bufResult.Length];
X> for (int i = 0; i < bufResult.Length; i++)
X> {
X> result[i] = Int32.Parse(bufResult[i]);
X> }
X> return result;
X> }
X> private static void PrintArray(int[] array)
X> {
X> foreach(int i in array)
X> {
X> Console.WriteLine(i);
X> }
X> }
X> private static int ff(int[] array)
X> {
X> int m = 1;
X> int buf = 0;
X> // общее количество сравнений (n-1)^2, где n - длина массива
X> for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X> {
X> // количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)
X> for (int j = 1; j < array.Length; j++)
X> {
X> if (array[0] == array[j])
X> {
X> buf = array[0];
X> goto result;
X> }
X> }
X> Swap(array, m);
X> m++;
X> }
X> result:
X> return buf;
X> }
X> private static void Swap(int[] array, int index)
X> {
X> int temp = array[index];
X> array[index] = array[0];
X> array[0] = temp;
X> }
X>
X>Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
X>
X>for (int j = 1; j < array.Length - 1; j++)
X>
X>при этом работа цикла
X>
X>for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X>
X>не прерывается
X>Заранее спасибо!
В подобных случаях, мне кажется, goto вполне оправдано
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Народ, чего-то много наворотили. Теорию не читаем?
Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
LVV>Народ, чего-то много наворотили. Теорию не читаем? LVV>Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
для поиска повторов не важно, целые ли числа.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Здравствуйте, Xobotik, Вы писали:
X>>>Условие задачи: X>>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>>число в этом массиве повторяется два раза. Найти это число за время O(N).
LVV>>Народ, чего-то много наворотили. Теорию не читаем? LVV>>Целые числа сортируются за время O(N) поразрядной сортировкой. И все. S>для поиска повторов не важно, целые ли числа.
Это принципиально. В постановке явно указано о целых именно поэтому.
Кроме того, можно за 1 проход исходного массива, имея массив размером М, найти это число.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, samius, Вы писали:
S>Здравствуйте, LaptevVV, Вы писали:
LVV>>Здравствуйте, Xobotik, Вы писали:
X>>>Условие задачи: X>>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>>число в этом массиве повторяется два раза. Найти это число за время O(N).
LVV>>Народ, чего-то много наворотили. Теорию не читаем? LVV>>Целые числа сортируются за время O(N) поразрядной сортировкой. И все. S>для поиска повторов не важно, целые ли числа.
А, понял! Ты имеешь ввиду, что два одинаковых вещественных все равно встанут рядом, если применить поразрядную сортировку к битовому представлению вещественных. Да, логично...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.
int[] a = {2, 2, 2, 2};
int i, j;
i = j = a.length - 1;
do {
i = a[i];
j = a[a[j]];
} while (i != j);
j = a.length - 1;
do {
i = a[i];
j = a[j];
} while (i != j);
System.out.println(i);
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, Xobotik, Вы писали:
vsb>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.
int[] a = { 1, 3, 2, 1, 4 };
выдает 4
Здравствуйте, samius, Вы писали:
S>Здравствуйте, vsb, Вы писали:
vsb>>Здравствуйте, Xobotik, Вы писали:
vsb>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>int[] a = { 1, 3, 2, 1, 4 }; S>выдает 4
N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, samius, Вы писали:
S>>Здравствуйте, vsb, Вы писали:
vsb>>>Здравствуйте, Xobotik, Вы писали:
vsb>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>>int[] a = { 1, 3, 2, 1, 4 }; S>>выдает 4
vsb>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
Здравствуйте, samius, Вы писали:
S>Здравствуйте, vsb, Вы писали:
vsb>>Здравствуйте, samius, Вы писали:
S>>>Здравствуйте, vsb, Вы писали:
vsb>>>>Здравствуйте, Xobotik, Вы писали:
vsb>>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>>>int[] a = { 1, 3, 2, 1, 4 }; S>>>выдает 4
vsb>>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
S>Вы условие задачи читали? Числа от 1-го до M!
Не придирайтесь Пусть будут от 0 до M-1, это ничего не изменит, если надо для исходной задачи — просто -1 написать в некоторых местах.
int[] a = { 1, 5, 1, 4, 3 };
int i, j;
i = j = a.length - 1;
do {
i = a[i] - 1;
j = a[a[j] - 1] - 1;
} while (i != j);
j = a.length - 1;
do {
i = a[i] - 1;
j = a[j] - 1;
} while (i != j);
System.out.println(i + 1);
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Как то так.
static int M = int.MaxValue;
static int BITS = (int)Math.Ceiling(Math.Log(M) / Math.Log(2));
static void Sort(ref int[] array)
{
int[] buffer = new int[array.Length];
for (int k = 0; k < BITS; ++k)
{
int mask = 1 << k;
int count = 0;
for (int i = 0; i < array.Length; ++i)
{
if ((array[i] & mask) == 0) ++count;
}
int min = 0;
for (int i = 0; i < array.Length; ++i)
{
if ((array[i] & mask) == 0)
{
buffer[min++] = array[i];
}
else buffer[count++] = array[i];
}
int[] temp = array;
array = buffer;
buffer = temp;
}
}
static void Main(string[] args)
{
int[] arr = new int[] { 5, 7, 2, 111, 4235, 0, 3, 11, 5251254, 9, 7 };
Sort(ref arr);
for(int i = 1; i < arr.Length; ++i)
{
if (arr[i - 1] == arr[i]) Console.WriteLine(arr[i]);
}
}
Требует O(N) дополнительной памяти и вообще говоря выполняется за время O(N * log M). Но в условии не сказано, что log M нельзя считать константой, и решение никак не должно зависеть от M. Полагаю это и не возможно.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
using System;
using System.Linq;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
var array = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, 15, 16, 17, 18, 19, 20 };
var duplicate = array.Sum(i => i) - GetProgressionSum(array.Length - 1, 1);
Console.WriteLine(duplicate);
}
static int GetProgressionSum(int length, int step)
{
var result = 0;
for (var i = 1; i <= length; i+=step)
{
result += i;
}
return result;
}
}
}
Re[2]: Поиск повторяющегося числа в массиве
От:
Аноним
Дата:
01.07.11 13:32
Оценка:
Здравствуйте, uxio, Вы писали:
U>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
могу на VB
DIM S(M) AS byte
DIM data(N) AS long
' заполняем data
.
.
FOR I = 1 TO N
if S( data(i) ) = 0 then
S( data(i) ) = 1
else
' повтор — ура нашли!
exit for
endif
next
msgbox S( data(i) )
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Как то лениво искать по всей ветке. Наверное вариант с xor уже звучал, да?
Здравствуйте, lastcross, Вы писали:
L>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
L>Как то лениво искать по всей ветке. Наверное вариант с xor уже звучал, да?
"Слышал звон, да не знает где он"(с)
XOR ищет из повторяющих — одно не повторяющееся, тут задача наоборот
Здравствуйте, elmal, Вы писали:
E>Здравствуйте, samius, Вы писали:
S>>Судя по всему речь о другой задаче, в которой все числа кроме одного встречаются четное число раз. E>Принцип тот же самый .
Принцип тот же самый?
И ты сходу такое решаешь? Да не гони.
Решал когда-то такую задачку на тестовое задание, но я принцип решения нагуглил.
Вот мой код:
#include"stdafx.h"#include <algorithm>
using namespace std;
typedef unsigned char BYTE;
//
// Random test array, containing 2 the same numbers.
//static unsigned test_array[] =
{
198, 258, 511, 173, 896, 415, 355, 71, 9012, 8, 15, 174, 886,
357, 422, 86, 114, 20, 544, 300, 2221, 41, 205, 278, 877, 66,
431, 30, 5002, 10, 54, 12, 82, 7019, 377, 4, 15906, 511, 123,
2233, 8018, 11, 20501, 911, 6034, 1111, 4448, 9876, 35461, 9,
8192,
};
const unsigned NumElementsInTestArray = sizeof( test_array ) / sizeof( unsigned int );
/*
******************************************************************************
*
* Function Name: CreateCounters()
*
* Function Purpose: Creates counter arrays.
*
* Function Description: Fill counter arrays with the amount of the numbers
* in the sorting array (data) with the given byte
* value for the each byte position.
* Arguments:
* unsigned * data - [in] Data that are going to be sorted.
* unsigned * counters - [out] Counters arrays.
* unsigned const N - [in] Number of elements in the data array.
*
*
* Return value: None.
*
* Revision History:
*
* 03/02/2009: Created.
*
******************************************************************************
*/static void CreateCounters( unsigned * data, unsigned * counters, unsigned const N )
{
//
// Counters array number i is placed at address ( counters + 256 * i )
//
memset(
counters,
0,
256 * sizeof( unsigned ) * sizeof( long )
);
BYTE * pb = ( BYTE* ) data;
BYTE * pbEnd = ( BYTE* )( data + N );
while( pb != pbEnd )
{
for( int i = 0; i < sizeof( unsigned ); i++, pb++ )
{
counters[ 256 * i + *pb ] ++ ;
}
}
}
/*
******************************************************************************
*
* Function Name: RadixPass()
*
* Function Purpose: One pass and sort for the given key position.
*
* Function Description:
*
* Arguments:
* int offset - [in] Key (byte) position (0..3);
* const long N - [in] Size of sorting array .
* unsigned * inArr - [in] Sorting array.
* unsigned * outArr - [out] Resulting array.
* unsigned * cntrArr - [in] Array of counters.
*
*
* Return value: None.
*
* Revision History:
*
* 03/02/2009: Created.
*
******************************************************************************
*/static void RadixPass( int offset,
const long N,
unsigned * inArr,
unsigned * outArr,
unsigned * cntrArr )
{
unsigned long sum = 0;
unsigned long tmp;
unsigned * pCntrArr = cntrArr;
const unsigned * const cntrEnd = cntrArr + 256;
for( ; pCntrArr != cntrEnd; pCntrArr++ )
{
tmp = *pCntrArr;
*pCntrArr = sum;
sum += tmp;
}
BYTE * pb = ( BYTE* )inArr + offset;
unsigned * pInArr = inArr;
for( int i = 0; i < N; i++, pb += sizeof( unsigned ), pInArr++ )
{
unsigned * pc = cntrArr + *pb;
outArr[ *pc ] = *pInArr;
( *pc )++;
}
}
/*
******************************************************************************
*
* Function Name: RadixSort()
*
* Function Purpose: Sorts array of unsigned integers.
*
* Function Description: Sort array of unsigned number by Radix Sort method.
* Bytes of the number are used as sorting keys.
*
* Arguments: unsigned * &inArr [in out] -
* Reference to pointer to source array.
*
* const long N [in] - Array size.
*
*
* Return value: None.
*
* Revision History:
*
* 03/02/2009: Created.
*
******************************************************************************
*/void RadixSort( unsigned * &inArr, const long N )
{
//
// One-dimension array is used for counters.
// Byte values is used as counter array index. Each element of counter
// array contains total amount of numbers with the given value of the byte.
// For each byte position (0,1,2,3) exists separate counters array.
//
// Placement counters in memory:
// -----------------------------------------------------------------------------
// 0s counters array | 1st cntrs. arr. | 2nd cntrs. arr. | 3rd cntrs. arr.
// -----------------------------------------------------------------------------
// [0] [256] [512] [768]
//unsigned counters[ sizeof( unsigned ) * 256 ];
unsigned * outArr = new unsigned[ N ];
CreateCounters(
inArr,
counters,
N
);
int swapCounter = 0; // need due to optimizationfor( int i = 0; i < sizeof( unsigned ); i++ )
{
unsigned * cntrsArr = counters + 256 * i;
//
// A little optimization: if all bytes in the current position are the same
// (equal to zero), sorting by this position is not required.
//if( N == counters[ 0 ] )
{
continue;
}
RadixPass(
i,
N,
inArr,
outArr,
cntrsArr
);
swap(
inArr,
outArr
);
swapCounter ++ ;
}
//
// Do not forget restore pointer to the incoming array if the number of swaps were odd !
//if( swapCounter & 1 )
{
swap(
inArr,
outArr
);
}
delete [] outArr;
}
//
// Application entry point.
//int main( int argc, char * argv[] )
{
unsigned * pArr = test_array;
unsigned dupNum = 0;
printf( "Original array:\n" );
for( int i = 1; i < NumElementsInTestArray; i++ )
{
printf( "%6d ", test_array[ i ] );
if( !( i % 10 ))
{
printf( "\n" );
}
}
RadixSort(
pArr,
NumElementsInTestArray
);
printf( "\n\nSorted array:\n" );
for( int i = 1; i < NumElementsInTestArray; i++ )
{
printf( "%6d ", test_array[ i ] );
if( !( i % 10 ))
{
printf( "\n" );
}
if( test_array[ i - 1 ] == test_array[ i ] )
{
dupNum = test_array[ i ];
}
}
printf(
"\n\n"
"Dublicate number found: %d\n",
dupNum
);
_getch();
return 0;
}
Здравствуйте, batu, Вы писали:
B>Здравствуйте, Xobotik, Вы писали:
X>>Здравствуйте, Don Reba, Вы писали:
DR>>>Здравствуйте, batu, Вы писали:
B>>>>В среднем O(3N/2) что явно лучше чем O(N)
DR>>>Несколько замечаний:
DR>>>1. 3N/2 > N DR>>>2. O(3N/2) = O(N) DR>>>3. Сложность алгоритма не О(N), а O(M), что может быть гораздо хуже.
X>>Отлично, ну а как тогда реализовывать поставленную задача, если алгоритм должен быть без сравнения и перебора элементов во вспомогательном массиве (так же без сравнения во входном массиве) за время O(N). Может быть в задаче, то и имелось ввиду за O(M). B>Видимо алгоритм не понят. B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, samius, Вы писали:
S>>Здравствуйте, -VladK-, Вы писали:
VK>>>Народ, да вы че? VK>>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!
S>>Разве в условии сказано что N = M + 1? S>>N = 10, M = 1000. Куда приложить прогрессию?
А>"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно А>число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.
N в общем случае не равняется M + 1, не? Намекаю другими словами, что в условии не сказано, что в массиве встечается каждое число от 1 до М.
Пример:
Здравствуйте, opener, Вы писали:
B>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.
O>Зачем ребенка неправильно учишь? O>Ну зарезервируй массив с диапазоном значений 4 миллиарда. "Офигенное" решение.
O>ЗЫ. А еще в условии не сказано, что числа положительные.
Так ребенок должен малость соображать, что это не для такого случая
Здравствуйте, batu, Вы писали:
B>Здравствуйте, opener, Вы писали:
B>>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.
O>>Зачем ребенка неправильно учишь? O>>Ну зарезервируй массив с диапазоном значений 4 миллиарда. "Офигенное" решение.
O>>ЗЫ. А еще в условии не сказано, что числа положительные. B>Так ребенок должен малость соображать, что это не для такого случая
Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.
Здравствуйте, opener, Вы писали:
O>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное.
Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..
Здравствуйте, batu, Вы писали:
B>Здравствуйте, opener, Вы писали:
O>>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное. B>Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..
B>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.
Твой совет? )
А теперь выполни его для такого массива:
Здравствуйте, opener, Вы писали:
O>Здравствуйте, batu, Вы писали:
B>>Здравствуйте, opener, Вы писали:
O>>>Дык ты ж ему изначально советуешь неправильно. Ты же для него гуру, твое мнение изначально авторитетное. B>>Насчет гуру и авторитетов то лестно.. но херня.. А насчет правильно-не правильно.. это зависит от реальной задачи..
B>>Мы резервируем массив размером с диапазон значений, и в цикле заносим единицу по индексу значения этого числа.
O>Твой совет? ) O>А теперь выполни его для такого массива:
O>
O>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>
Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.
Здравствуйте, batu, Вы писали:
B>Здравствуйте, opener, Вы писали:
O>>
O>>unsigned arr[] = { 1, 2, 3, 0xFFFFFFFF };
O>>
B>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами.
Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?
B>>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами. S>Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?
B>>Та запросто. Сначала пронумеровать, и выполнить тоже самое с номерами. S>Зачем выполнять то же самое, если в процессе нумерации решение уже будет найдено?
Есть и такой вариант. Смотря как задача поставлена
Re[12]: Решение за O(N) и доп. память O(N)
От:
Аноним
Дата:
22.07.11 10:44
Оценка:
Здравствуйте, Xobotik, Вы писали:
X>Здравствуйте, OlegMax, Вы писали:
OM>>Попробуем мысленно прогнать на последовательности {3,3}. Получим "index out of bounds".
X>Ну тогда буферный массив будет выглядеть следующим образом: X>
X>int[] buf = new int[array.Max() + 1];
X>
Что за чушь? Пусть array.Max() == 0xFFFFFFFF
Дальше что?
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
X>Реализация: X>
X>private static string separator = ";";
X> static void Main(string[] args)
X> {
X> int[] result = GetIntArray(InputArray());
X> PrintArray(result);
X> Console.WriteLine(ff(result));
X> Console.ReadLine();
X> }
X> private static string InputArray()
X> {
X> Console.WriteLine("Введите массив, содержащий только целые числа.");
X> Console.WriteLine("После каждого числа ставьте разделитель '{0}'", separator);
X> Console.WriteLine("Введите массив: ");
X> return Console.In.ReadLine();
X> }
X> private static int[] GetIntArray(string insert)
X> {
X> string pattern = String.Format("{0}(?=(?:[^\"]*\"[^\"]*\")*(?![^\"]*\"))", separator);
X> string[] bufResult = Regex.Split(insert, pattern);
X> int[] result = new int[bufResult.Length];
X> for (int i = 0; i < bufResult.Length; i++)
X> {
X> result[i] = Int32.Parse(bufResult[i]);
X> }
X> return result;
X> }
X> private static void PrintArray(int[] array)
X> {
X> foreach(int i in array)
X> {
X> Console.WriteLine(i);
X> }
X> }
X> private static int ff(int[] array)
X> {
X> int m = 1;
X> int buf = 0;
X> // общее количество сравнений (n-1)^2, где n - длина массива
X> for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X> {
X> // количество перестановок (n-1) = количеству сравнений array[0] и array[k], где k - числа от 1 до n (n - длина массива)
X> for (int j = 1; j < array.Length; j++)
X> {
X> if (array[0] == array[j])
X> {
X> buf = array[0];
X> goto result;
X> }
X> }
X> Swap(array, m);
X> m++;
X> }
X> result:
X> return buf;
X> }
X> private static void Swap(int[] array, int index)
X> {
X> int temp = array[index];
X> array[index] = array[0];
X> array[0] = temp;
X> }
X>
X>Есть ли какие-либо другие пути решения задачи? Без goto не вижу решения задачи, если использовать break, там где buf = array[0] , останавливается только цикл:
X>
X>for (int j = 1; j < array.Length - 1; j++)
X>
X>при этом работа цикла
X>
X>for (int i = 0; i < (array.Length - 1) * (array.Length - 1); i++)
X>
X>не прерывается
X>Заранее спасибо!
Реализация на с
int Find(int * Array,int N, int M)
{
int *AsPresent = new int[M];
memset(AsPresent,0,sizeof(int)*M);
for(int i=0;i<N;i++)
if(AsPresent[Array[i]])
{
delete[] AsPresent;
return Array[i];
}
else
AsPresent[Array[i]] = 1;
delete[] AsPresent;
return -1;
}
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, samius, Вы писали:
S>>Здравствуйте, vsb, Вы писали:
vsb>>>Здравствуйте, samius, Вы писали:
S>>>>Здравствуйте, vsb, Вы писали:
vsb>>>>>Здравствуйте, Xobotik, Вы писали:
vsb>>>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>>>>int[] a = { 1, 3, 2, 1, 4 }; S>>>>выдает 4
vsb>>>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
S>>Вы условие задачи читали? Числа от 1-го до M!
vsb>Не придирайтесь Пусть будут от 0 до M-1, это ничего не изменит, если надо для исходной задачи — просто -1 написать в некоторых местах.
Никто и не придирается. Просто твое решение неправильное, вот и все.
Здравствуйте, opener, Вы писали:
O>Здравствуйте, vsb, Вы писали:
vsb>>Здравствуйте, samius, Вы писали:
S>>>Здравствуйте, vsb, Вы писали:
vsb>>>>Здравствуйте, samius, Вы писали:
S>>>>>Здравствуйте, vsb, Вы писали:
vsb>>>>>>Здравствуйте, Xobotik, Вы писали:
vsb>>>>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>>>>>int[] a = { 1, 3, 2, 1, 4 }; S>>>>>выдает 4
vsb>>>>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
S>>>Вы условие задачи читали? Числа от 1-го до M!
vsb>>Не придирайтесь Пусть будут от 0 до M-1, это ничего не изменит, если надо для исходной задачи — просто -1 написать в некоторых местах.
O>Никто и не придирается. Просто твое решение неправильное, вот и все.
На каких входных данных моё решение даёт неверный ответ?
Здравствуйте, opener, Вы писали:
O>Здравствуйте, SergeySymbol, Вы писали:
SS>>Реализация на с SS>>
SS>>int Find(int * Array,int N, int M)
SS>>{
SS>> int *AsPresent = new int[M];
SS>> memset(AsPresent,0,sizeof(int)*M);
SS>> for(int i=0;i<N;i++)
SS>> if(AsPresent[Array[i]])
SS>> {
SS>> delete[] AsPresent;
SS>> return Array[i];
SS>> }
SS>> else
SS>> AsPresent[Array[i]] = 1;
SS>> delete[] AsPresent;
SS>> return -1;
SS>>}
SS>>
O>Клево. O>Особенно умиляет количество памяти, которое необходимо выделить, для такого, к примеру, массива:
O>
O>int Array[] = { 1, 1, 0xFFFFFFFF };
O>
Приведенный массив не соответствует условию задачи поскольку ты скорее всего имел ввиду int 32 разрядный целочисленный знаковый тип то значение 0xFFFFFFFF будет интерпретировано как -1, а в условии от 1 до M. Да слабость этого алгоритма в выделении дополнительной памяти, а так если не считать memset(AsPresent,0,sizeof(int)*M) то он удовлетворяет условию O(N).
если использовать в качестве словаря контейнеры на основе бинарных деревьев , то сложность будет O(N*log(N)).
Здравствуйте, SergeySymbol, Вы писали:
SS>Приведенный массив не соответствует условию задачи поскольку ты скорее всего имел ввиду int 32 разрядный целочисленный знаковый тип то значение 0xFFFFFFFF будет интерпретировано как -1, а в условии от 1 до M. Да слабость этого алгоритма в выделении дополнительной памяти, а так если не считать memset(AsPresent,0,sizeof(int)*M) то он удовлетворяет условию O(N). SS>если использовать в качестве словаря контейнеры на основе бинарных деревьев , то сложность будет O(N*log(N)).
Как это "не считать"? Инициализация этой памяти займёт O(M), а значит сложность будет O(M+N).
Здравствуйте, Don Reba, Вы писали:
DR>Здравствуйте, SergeySymbol, Вы писали:
SS>>Приведенный массив не соответствует условию задачи поскольку ты скорее всего имел ввиду int 32 разрядный целочисленный знаковый тип то значение 0xFFFFFFFF будет интерпретировано как -1, а в условии от 1 до M. Да слабость этого алгоритма в выделении дополнительной памяти, а так если не считать memset(AsPresent,0,sizeof(int)*M) то он удовлетворяет условию O(N). SS>>если использовать в качестве словаря контейнеры на основе бинарных деревьев , то сложность будет O(N*log(N)).
DR>Как это "не считать"? Инициализация этой памяти займёт O(M), а значит сложность будет O(M+N).
так я это и указал.
Здравствуйте, vsb, Вы писали:
vsb>Здравствуйте, opener, Вы писали:
O>>Здравствуйте, vsb, Вы писали:
vsb>>>Здравствуйте, samius, Вы писали:
S>>>>Здравствуйте, vsb, Вы писали:
vsb>>>>>Здравствуйте, samius, Вы писали:
S>>>>>>Здравствуйте, vsb, Вы писали:
vsb>>>>>>>Здравствуйте, Xobotik, Вы писали:
vsb>>>>>>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз. S>>>>>>int[] a = { 1, 3, 2, 1, 4 }; S>>>>>>выдает 4
vsb>>>>>N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
S>>>>Вы условие задачи читали? Числа от 1-го до M!
vsb>>>Не придирайтесь Пусть будут от 0 до M-1, это ничего не изменит, если надо для исходной задачи — просто -1 написать в некоторых местах.
O>>Никто и не придирается. Просто твое решение неправильное, вот и все.
vsb>На каких входных данных моё решение даёт неверный ответ?
Задача же решается одним лишь вызовом array.Sum() и несколькими математическими операциями, никак не связанными с массивом. Другими словами, то, как в данной задаче вычислить "array.Distinct().Sum()" объяснялось в пятом классе средней школы и я выше даже приводил ссылку на решение.
