Здравствуйте, 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, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.