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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
#1

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

01.08.2013, 10:46. Просмотров 966. Ответов 14
Метки нет (Все метки)

Вопрос для людей, который разбираются в теории. Ну или знаю на практике, какой способ является быстрым для упорядоченного массива с дубликатами.
Я вот такую функцию написал.
Кликните здесь для просмотра всего текста
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;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.08.2013, 10:46     Найти количество дубликатов в массиве
Посмотрите здесь:

Проверка дубликатов в массиве при вводе - C++
Приветствую. Задача: разрешить ввод элемента только в том случае, если такого элемента массива еще нет + сортировка простым поиском. ...

Найти в массиве максимальный и минимальный элементы в массиве и их количество - C++
Помогите, пожалуйста, начал осваивать c++...Не могу справиться с такой задачей: Написать программу, которая вводит с клавиатуры массив...

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

Найти количество повторов в массиве - C++
Как найти количиство повторов в массиве длиной вводимой с клавы? О_о

Найти количество нулей на интервале от а до b в массиве - C++
найти количество нулей на интервале то а до b в масcиве ( где а и b числа в масcиве) Например, массив 1, 2, 0, 3, 4, 0, 6 если а=2...

Найти количество нулей в двумерном массиве - C++
Написать программу, которая случайным образом заполняет двумерный массив размерностью 3х4 цифрами от 0 до 10. Необходимо найти...

Найти количество отрицательных элементов в массиве - C++
Здравствуйте! Просьба к знающим,если не сложно,помочь решить одну задачу. Дано два массива Y(n) и X(m). C помощью функции найти...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
01.08.2013, 10:56     Найти количество дубликатов в массиве #2
у вас верхняя оценка квадратичная. легко считается за линию. т.к. массив упорядочен, одинаковые стоят рядом. тогда для ai ответом будет: (a[i] == a[i-1] ? ans[i-1] + 1 : 0).
nonedark2008
889 / 628 / 126
Регистрация: 28.07.2012
Сообщений: 1,697
01.08.2013, 10:57     Найти количество дубликатов в массиве #3
Цитата Сообщение от Maxak Посмотреть сообщение
для упорядоченного массива с дубликатами
Ну дык, если массив уже упорядочен, то все дубликаты должны находиться рядом. Т.е. не нужно проверять все элементы, а только ближайшие к проверяемому.
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
01.08.2013, 11:21     Найти количество дубликатов в массиве #8
Цитата Сообщение от salam Посмотреть сообщение
массивчик такой нужно посчитать.
по нему легко восстановить, сколько и чего было в исходном массиве.

Добавлено через 1 минуту
но это, конечно, если речь идет о быстром решении. то, о чем я говорил работает за O(N). однако есть совсем простой способ с std::map. он будет стоить вам O(n*logn).
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
01.08.2013, 11:21     Найти количество дубликатов в массиве #9
Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано)
1,1,2,2 -> должен вернуть 2?
1,1,1,2 -> должен вернуть 3?
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
01.08.2013, 12:24     Найти количество дубликатов в массиве #12
Цитата Сообщение от Maxak Посмотреть сообщение
Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".
Что-то я уже не уверен, что "1,1,1,2" должно вернуть "3"
Есть наиболее полная формулировка задачи?
salam
162 / 143 / 12
Регистрация: 10.07.2012
Сообщений: 725
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     Найти количество дубликатов в массиве
Еще ссылки по теме:

Найти количество чётных элементов в массиве - C++
Массив кол-во элементов 12. Значение элементов от 2 до ... с шагом 2. Найти кол-во чётных элементов.

Найти количество нечётных цифр в массиве - C++
Введены цифры , нужно найти сколько из них нечётные числа. Нужно использывать массивы.

Найти количество различных элементов в массиве - C++
Дан целочисленный массив размера N, все элементы которого упоря-дочены (по возрастанию или по убыванию). Найти количество различных...

Найти количество различных элементов в массиве. - 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     Найти количество дубликатов в массиве
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru