Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

В массиве записаны оценки, найти количество пятерок, количество четверок, количество троек и количество двоек - C++
В массиве записаны оценки по иностранному языку каждого из 22 учеников класса. Определить количество пятерок, количество четверок,...

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

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

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

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

Найти количество слов в символьном массиве - C++
дано: х (100), найти количество слов в символьном массиве. Очень прошу помогите...!!!

14
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
01.08.2013, 10:56 #2
у вас верхняя оценка квадратичная. легко считается за линию. т.к. массив упорядочен, одинаковые стоят рядом. тогда для ai ответом будет: (a[i] == a[i-1] ? ans[i-1] + 1 : 0).
1
nonedark2008
964 / 704 / 157
Регистрация: 28.07.2012
Сообщений: 1,929
01.08.2013, 10:57 #3
Цитата Сообщение от Maxak Посмотреть сообщение
для упорядоченного массива с дубликатами
Ну дык, если массив уже упорядочен, то все дубликаты должны находиться рядом. Т.е. не нужно проверять все элементы, а только ближайшие к проверяемому.
1
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
01.08.2013, 10:58 #4
std::equal_range + std::distance, или, тупо, std::count (но тогда придется весь массив пробежать)
0
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]?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
01.08.2013, 11:15 #6
ansi - количество элементов, равных ai, не считая его самого. массивчик такой нужно посчитать.
0
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;
}
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
01.08.2013, 11:21 #8
Цитата Сообщение от salam Посмотреть сообщение
массивчик такой нужно посчитать.
по нему легко восстановить, сколько и чего было в исходном массиве.

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

Добавлено через 1 минуту
только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.
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 Посмотреть сообщение
только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.
Да, может вы и правы сейчас пересмотрю общую задачу. Может я не правильно сделал декомпозицию задачи.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
01.08.2013, 12:24 #12
Цитата Сообщение от Maxak Посмотреть сообщение
Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".
Что-то я уже не уверен, что "1,1,1,2" должно вернуть "3"
Есть наиболее полная формулировка задачи?
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
01.08.2013, 13:08 #13
дело в том, что массивчик ans[] решает более общую задачу. имея его, вы можете сказать, каких сколько и сколько уникальных тоже.
0
Maxak
0 / 0 / 0
Регистрация: 27.12.2012
Сообщений: 47
01.08.2013, 13:13  [ТС] #14
обобщил задачу
Выделить из упорядоченного массива подмассив ограниченный точками x1, x2
0
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++;
    }
И будет вам количество дубликатов.
0
01.08.2013, 13:40
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.08.2013, 13:40
Привет! Вот еще темы с ответами:

Найти количество различных элементов в массиве. - C++
Найти количество различных элементов в массиве.

Найти количество элементов, равных 2, в массиве - C++
Привет. Застрял на программе с поиском одинаковых элементов в массиве. Нужно найти количество цифр &quot;2&quot; в массиве. Помогите понять суть...

Найти количество нулей в одномерном массиве - C++
Добрый день! Суть задачи : Найти количество нулей в одномерном массиве А Помогите исправить задачку . Программа работает не правильно....

Найти количество простых чисел в массиве - C++
Дано N мерное массивное число. Есть ли среди массивом простое число? Если есть то нужно вывести число этих элементов.


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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