Форум программистов, компьютерный форум CyberForum.ru

Алгоритм поиска одинаковых элементов - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.64
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
20.07.2013, 18:47     Алгоритм поиска одинаковых элементов #1
Подскажите какой-нибудть алгоритм (реализацию писать не надо)

Есть числовые записи в файле
грубо говоря

1 4 6 8
3 5 14 27
1 2 4 6 17
3 5 6 14

Нужен алгоритм который найдет все пары одинаковых чисел во всех записях
т.е в данном случае у первой записи и у 2 ой - нету пар, у первой и 3-ей 1 - 4 - 6 и тд....
Сложность не более O(N2)...

Подскажите в сторону чего смотреть....
Спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vxg
Модератор
 Аватар для vxg
2662 / 1673 / 157
Регистрация: 13.01.2012
Сообщений: 6,223
20.07.2013, 19:08     Алгоритм поиска одинаковых элементов #2
1 заводим массив списков номеров записей содержащий столько элементов сколько у нас может быть цифр (как вариант - в начале проходим по всем записям и ищем максимальное число)
2 проходим по всем записям и кладем номер записи в список под номером цифры
3 очевидно, что все возможные сочетания в пределах каждого списка являются всеми возможными парами
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
20.07.2013, 19:35  [ТС]     Алгоритм поиска одинаковых элементов #3
не понял второй пункт..., а именно "кладем номер записи в список под номером цифры"
читаем файл - первая запись 1 4 6 8 и ???.... номер записи один (ну или 0 если списки записей в массиве)
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
20.07.2013, 19:44     Алгоритм поиска одинаковых элементов #4
Dark2013, если можно юзать сложность O(n^2), то просто проходи по всем числам со всем записей цикл в цикле как-то так:
C++
1
2
for (int i = 0; i<n; ++i)
   for (int j = 0; j<n; ++j)
И ищи пару числу A[i] (где A - число с номером i в последовательности, которую можно получить, если записать все записи подряд)

Добавлено через 1 минуту
Dark2013, vxg вероятно хотел сказать, что, если известно минимальное и максимальное числа, которые могут быть в записях, то просто можно создать массив списков A, в котором A[i] будет означать список позиций, в которых встретилось число i. Основываясь на этих списках и можно вывести все пары.
Dark2013
0 / 0 / 0
Регистрация: 02.02.2013
Сообщений: 7
20.07.2013, 19:55  [ТС]     Алгоритм поиска одинаковых элементов #5
ага)) Это ты найдеш только для одной записи....а тебе нужно для всех....
- добавляй еще один цикл - получится полный перебор O(N3)

вроде начинаю врубаться... ща запилю
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
20.07.2013, 22:17     Алгоритм поиска одинаковых элементов #6
Цитата Сообщение от Dark2013 Посмотреть сообщение
Сложность не более O(N2)...
А N это что? число всех элементов? Тогда трудно придумать что-то, что превысит O(N^2). Вот если бы условие стояло: сложность не выше O(N ln N) или даже не выше линейной, тогда - другое дело.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
20.07.2013, 23:43     Алгоритм поиска одинаковых элементов #7
Цитата Сообщение от Dark2013 Посмотреть сообщение
- добавляй еще один цикл - получится полный перебор O(N3)
куда еще 1 цикл? В моем алго N - кол-во элементов во всех записях. Я подразумеваю, что ты думаешь это:
C++
1
2
for (int l = 0; l<xx; ++l) //выбираем номер списка
    for (int i = 0; i<length[xx]; ++i) //перебираем числа в списке
От добавления этого сложность не изменится: мы просто проходим по всем элементам. Есть двумерный массив из 3 столбцов и 5 строк - итого 15 элементов и есть обычный линейный массив из 15 элементов. По твоей логике, чтобы пройтись по элементам одномерного массива я могу за линейное время, а по двумерному - за квадрат?
vxg
Модератор
 Аватар для vxg
2662 / 1673 / 157
Регистрация: 13.01.2012
Сообщений: 6,223
21.07.2013, 08:22     Алгоритм поиска одинаковых элементов #8
Цитата Сообщение от Dani Посмотреть сообщение
vxg вероятно хотел сказать, что, если известно минимальное и максимальное числа, которые могут быть в записях, то просто можно создать массив списков A, в котором A[i] будет означать список позиций, в которых встретилось число i. Основываясь на этих списках и можно вывести все пары.
точно. именно так. причем сложность будет никакой - нужно просто один раз пройти все записи (или если минимум и максимум не известные три раза). после этого вывод всех возможных сочетаний - механическая операция сложность которой, наверное, можно не включать в общую сложность алгоритма
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
21.07.2013, 08:22     Алгоритм поиска одинаковых элементов #9
у вас случайно числа в записях упорядочены?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.07.2013, 08:34     Алгоритм поиска одинаковых элементов
Еще ссылки по теме:

C++ Алгоритм поиска
C++ Простые алгоритм поиска?
C++ Замена первой группы одинаковых элементов на последнюю группу одинаковых элементов

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
21.07.2013, 08:34     Алгоритм поиска одинаковых элементов #10
Цитата Сообщение от salam Посмотреть сообщение
у вас случайно числа в записях упорядочены?

Не по теме:

вот и я намекаю, что при определенном раскладе сложность гораздо меньше будет



Цитата Сообщение от Dani Посмотреть сообщение
C++
1
2
for (int l = 0; l<xx; ++l) //выбираем номер списка
    for (int i = 0; i<length[xx]; ++i) //перебираем числа в списке
по условию задачи, надо перебирать числа во всех предыдущих списках (поэтому три цикла), судя по примеру, но от этого сложность алгоритма не меняется.
Yandex
Объявления
21.07.2013, 08:34     Алгоритм поиска одинаковых элементов
Ответ Создать тему
Опции темы

Текущее время: 21:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru