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

Найти количество дубликатов в массиве - C++

Восстановить пароль Регистрация
 
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 10:46     Найти количество дубликатов в массиве #1
Вопрос для людей, который разбираются в теории. Ну или знаю на практике, какой способ является быстрым для упорядоченного массива с дубликатами.
Я вот такую функцию написал.
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<class T>
int dublicat_count_in_arr(const T *H, int N)
{
    int dublicat_count = 0;
    for(int i=0; i=N-1; i++)
    {
        int j=N;
        while(j!=i)
        {
        if(H[i] == H[j]) dublicat_count++;
        j--;
        }
    }
    return dublicat_count;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 10:56     Найти количество дубликатов в массиве #2
у вас верхняя оценка квадратичная. легко считается за линию. т.к. массив упорядочен, одинаковые стоят рядом. тогда для ai ответом будет: (a[i] == a[i-1] ? ans[i-1] + 1 : 0).
nonedark2008
624 / 502 / 92
Регистрация: 28.07.2012
Сообщений: 1,343
01.08.2013, 10:57     Найти количество дубликатов в массиве #3
Цитата Сообщение от Maxak Посмотреть сообщение
для упорядоченного массива с дубликатами
Ну дык, если массив уже упорядочен, то все дубликаты должны находиться рядом. Т.е. не нужно проверять все элементы, а только ближайшие к проверяемому.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
01.08.2013, 10:58     Найти количество дубликатов в массиве #4
std::equal_range + std::distance, или, тупо, std::count (но тогда придется весь массив пробежать)
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 11:10  [ТС]     Найти количество дубликатов в массиве #5
Цитата Сообщение от salam Посмотреть сообщение
(a[i] == a[i-1] ? ans[i-1] + 1 : 0).
идею понял, а что такое ans[i-1]?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 11:15     Найти количество дубликатов в массиве #6
ansi - количество элементов, равных ai, не считая его самого. массивчик такой нужно посчитать.
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 11:16  [ТС]     Найти количество дубликатов в массиве #7
Реализация так вот будет выглядеть, как я понял?
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class T>
int dublicat_count_in_arr(const T *H, int N)
{
    int dublicat_count = 0;
    for(int i=0; i=N-1; i++)
    {
        while(H[i] == H[i+1])
        {
            i++;
            dublicat_count++;
        }
    }
    return dublicat_count;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 11:21     Найти количество дубликатов в массиве #8
Цитата Сообщение от salam Посмотреть сообщение
массивчик такой нужно посчитать.
по нему легко восстановить, сколько и чего было в исходном массиве.

Добавлено через 1 минуту
но это, конечно, если речь идет о быстром решении. то, о чем я говорил работает за O(N). однако есть совсем простой способ с std::map. он будет стоить вам O(n*logn).
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
01.08.2013, 11:21     Найти количество дубликатов в массиве #9
Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано)
1,1,2,2 -> должен вернуть 2?
1,1,1,2 -> должен вернуть 3?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 11:25     Найти количество дубликатов в массиве #10
Цитата Сообщение от Maxak Посмотреть сообщение
Реализация так вот будет выглядеть, как я понял?
да. очевидно, он тоже линеен. при том без доп. памяти.

Добавлено через 1 минуту
только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 11:35  [ТС]     Найти количество дубликатов в массиве #11
Цитата Сообщение от Tulosba Посмотреть сообщение
Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано)
ага, спасибо.
Цитата Сообщение от Tulosba Посмотреть сообщение
Maxak, 1,1,2,2 -> должен вернуть 2?
1,1,1,2 -> должен вернуть 3?
Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".

Добавлено через 1 минуту
Цитата Сообщение от salam Посмотреть сообщение
только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.
Да, может вы и правы сейчас пересмотрю общую задачу. Может я не правильно сделал декомпозицию задачи.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
01.08.2013, 12:24     Найти количество дубликатов в массиве #12
Цитата Сообщение от Maxak Посмотреть сообщение
Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".
Что-то я уже не уверен, что "1,1,1,2" должно вернуть "3"
Есть наиболее полная формулировка задачи?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
01.08.2013, 13:08     Найти количество дубликатов в массиве #13
дело в том, что массивчик ans[] решает более общую задачу. имея его, вы можете сказать, каких сколько и сколько уникальных тоже.
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 13:13  [ТС]     Найти количество дубликатов в массиве #14
обобщил задачу
Выделить из упорядоченного массива подмассив ограниченный точками x1, x2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2013, 13:40     Найти количество дубликатов в массиве
Еще ссылки по теме:

В массиве Z (m) найти количество дежурств знака, то есть количество переходов с минуса на плюс и наоборот. Например, в последовательности 0, - 2, 0 - C++
Найти в массиве количество элементов меньше 5 C++
C++ Найти количество отрицательных элементов в массиве

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

Или воспользуйтесь поиском по форуму:
iel
1 / 1 / 0
Регистрация: 30.07.2013
Сообщений: 15
01.08.2013, 13:40     Найти количество дубликатов в массиве #15
Это ещё что за нафиг?
C++
1
for(int i=0; i=N-1; i++)
Если массив упорядочен, то строки 6-14 в исходнике надо заменить на следующий код:
C++
1
2
3
4
5
6
    N--;
    for (int i = 0; i < N; i++)
    {
        if (H[i] == H[i + 1])
            dublicat_count++;
    }
И будет вам количество дубликатов.
Yandex
Объявления
01.08.2013, 13:40     Найти количество дубликатов в массиве
Ответ Создать тему
Опции темы

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