Здравствуйте, 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).
Я имел ввиду, что алгоритм в среднем требует половины цикла. Как-то надо было разделить пополам
