Re: Поиск повторяющегося числа в массиве
От: lxa http://aliakseis.livejournal.com
Дата: 04.05.10 08:53
Оценка: 9 (2)
Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:

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

X>...


X>Есть ли какие-либо другие пути решения задачи?


Вот нагуглилось что-то вроде интересное:
http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html
Re[2]: Поиск повторяющегося числа в массиве
От: andy1618 Россия  
Дата: 04.05.10 22:48
Оценка:
Здравствуйте, lxa, Вы писали:

lxa>Вот нагуглилось что-то вроде интересное:

lxa>http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html

Классная ссылка! Последний подход (с обнаружением цикла у графа методом "догонялок") красивый, но он не будет работать для той трактовки задачи, когда N < M+1 (например, на упомянутом выше массиве: { 1, 500, 600, 1 } ).
Т.е. пока что все решения для такой трактовки требуют доп. память.
Re[8]: Поиск повторяющегося числа в массиве
От: Xobotik Россия  
Дата: 10.05.10 22:41
Оценка:
Здравствуйте, 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. я мог ошибиться в размышлениях, заранее сорри.
С уважением!
Re[11]: Решение за O(N) и доп. память O(N)
От: Xobotik Россия  
Дата: 12.05.10 07:44
Оценка:
Здравствуйте, OlegMax, Вы писали:

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


Ну тогда буферный массив будет выглядеть следующим образом:
int[] buf = new int[array.Max() + 1];
С уважением!
Re[10]: Решение за O(N) и доп. память O(N)
От: Dufrenite Дания  
Дата: 20.08.10 14:37
Оценка:
Здравствуйте, Xobotik, Вы писали:

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


X>здесь
Автор: Xobotik
Дата: 03.04.10


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


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


Ошибка в программе. Тебе на неё указали, ты проигнорировал.

Напиши и запусти:


void Main()
{
  foo(new int[] { 1000, 1000 });
}
Re: Поиск повторяющегося числа в массиве
От: Аноним  
Дата: 09.09.10 12:46
Оценка: -1 :)
Здравствуйте, Xobotik, Вы писали:

оверквотинг — зло.

Пройит в цикле по массиву и отXORить числа, повт. дадут нуль
Re[2]: Поиск повторяющегося числа в массиве
От: samius Япония http://sams-tricks.blogspot.com
Дата: 09.09.10 17:35
Оценка:
Здравствуйте, Аноним, Вы писали:

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


А>Пройит в цикле по массиву и отXORить числа, повт. дадут нуль


Каждое с каждым ксорить что ли?

а другие варианты какие? Подряд все ксорить?

xor(1, 2, 3) даст 0.
Re: Поиск повторяющегося числа в массиве
От: batu Украина  
Дата: 09.09.10 20:28
Оценка: -1
Здравствуйте, Xobotik, Вы писали:


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
Re[2]: Поиск повторяющегося числа в массиве
От: blackhearted Украина  
Дата: 10.09.10 15:01
Оценка:
Здравствуйте, andy1618, Вы писали:

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


X>>Условие задачи:

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

A>Кстати, интересно, а откуда эта задачка?


Похоже на гуглособеседование по телефону.
Re: Поиск повторяющегося числа в массиве
От: Hamlet Армения  
Дата: 11.09.10 19:29
Оценка: -1 :))
Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:

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

Решение тривиально. Заводим массив бит ММ с размером M инициализируя нульями.
Пробегая через массив с размером N усатавливаем соответствующий бит (тоесть n-ный бит, где n текущий элемент из N)
в массиве ММ если неустановлен, иначе текущий элемент искомый.
Re[2]: Поиск повторяющегося числа в массиве
От: dilmah США  
Дата: 11.09.10 19:50
Оценка:
слушай, ты настоящий Кэп, не могу подобрать точный титул
Re: Поиск повторяющегося числа в массиве
От: zdv Россия  
Дата: 11.05.11 07:01
Оценка:
Здравствуйте, 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 вполне оправдано
С уважением, Дмитрий
Re: Поиск повторяющегося числа в массиве
От: LaptevVV Россия  
Дата: 11.05.11 07:05
Оценка: 20 (3) +1
Здравствуйте, Xobotik, Вы писали:

X>Условие задачи:

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

Народ, чего-то много наворотили. Теорию не читаем?
Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[2]: Поиск повторяющегося числа в массиве
От: samius Япония http://sams-tricks.blogspot.com
Дата: 11.05.11 07:29
Оценка:
Здравствуйте, LaptevVV, Вы писали:

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


X>>Условие задачи:

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

LVV>Народ, чего-то много наворотили. Теорию не читаем?

LVV>Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
для поиска повторов не важно, целые ли числа.
Re[3]: Поиск повторяющегося числа в массиве
От: B0FEE664  
Дата: 11.05.11 11:03
Оценка:
Здравствуйте, dilmah, Вы писали:

D>слушай, ты настоящий Кэп, не могу подобрать точный титул


Кэп подсказывает, что если:
"число в этом массиве повторяется два раза"
то встречается оно трижды
так?
И каждый день — без права на ошибку...
Re[3]: Поиск повторяющегося числа в массиве
От: LaptevVV Россия  
Дата: 11.05.11 12:08
Оценка:
Здравствуйте, samius, Вы писали:

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


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


X>>>Условие задачи:

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

LVV>>Народ, чего-то много наворотили. Теорию не читаем?

LVV>>Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
S>для поиска повторов не важно, целые ли числа.
Это принципиально. В постановке явно указано о целых именно поэтому.
Кроме того, можно за 1 проход исходного массива, имея массив размером М, найти это число.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re[3]: Поиск повторяющегося числа в массиве
От: LaptevVV Россия  
Дата: 11.05.11 12:20
Оценка: +2
Здравствуйте, samius, Вы писали:

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


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


X>>>Условие задачи:

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

LVV>>Народ, чего-то много наворотили. Теорию не читаем?

LVV>>Целые числа сортируются за время O(N) поразрядной сортировкой. И все.
S>для поиска повторов не важно, целые ли числа.
А, понял! Ты имеешь ввиду, что два одинаковых вещественных все равно встанут рядом, если применить поразрядную сортировку к битовому представлению вещественных. Да, логично...
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Re: Поиск повторяющегося числа в массиве
От: vsb Казахстан  
Дата: 13.05.11 06:22
Оценка: -1 :)
Здравствуйте, 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);
Re[2]: Поиск повторяющегося числа в массиве
От: samius Япония http://sams-tricks.blogspot.com
Дата: 13.05.11 06:36
Оценка:
Здравствуйте, vsb, Вы писали:

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


vsb>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.

int[] a = { 1, 3, 2, 1, 4 };
выдает 4
Re[3]: Поиск повторяющегося числа в массиве
От: vsb Казахстан  
Дата: 13.05.11 06:41
Оценка: -1 :)
Здравствуйте, samius, Вы писали:

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


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


vsb>>Если M < N, то вот решение. Не выделяет лишней памяти, не изменяет исходный массив. Печатает одно из чисел, которые повторяются 2 или более раз.

S>int[] a = { 1, 3, 2, 1, 4 };
S>выдает 4

N = 5, M = 5, условие не удовлетворено. В общем цифры надо считать с нуля. Если каждое число в вашем примере уменьшить на единицу, то всё работает.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.