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

@Maxak · Регистрация: 27.12.2012

Студворк — интернет-сервис помощи студентам

Вопрос для людей, который разбираются в теории. Ну или знаю на практике, какой способ является быстрым для упорядоченного массива с дубликатами.
Я вот такую функцию написал.

Кликните здесь для просмотра всего текста

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 · 01.08.2013, 10:56

у вас верхняя оценка квадратичная. легко считается за линию. т.к. массив упорядочен, одинаковые стоят рядом. тогда для a_i ответом будет: (a[i] == a[i-1] ? ans[i-1] + 1 : 0).

@nonedark2008 · 01.08.2013, 10:57

Сообщение от Maxak

для упорядоченного массива с дубликатами

Ну дык, если массив уже упорядочен, то все дубликаты должны находиться рядом. Т.е. не нужно проверять все элементы, а только ближайшие к проверяемому.

Tulosba · 01.08.2013, 10:58

std::equal_range + std::distance, или, тупо, std::count (но тогда придется весь массив пробежать)

@Maxak · 01.08.2013, 11:10 **[ТС]**

Сообщение от salam

(a[i] == a[i-1] ? ans[i-1] + 1 : 0).

идею понял, а что такое ans[i-1]?

@salam · 01.08.2013, 11:15

ans_i - количество элементов, равных a_i, не считая его самого. массивчик такой нужно посчитать.

@Maxak · 01.08.2013, 11:16 **[ТС]**

Реализация так вот будет выглядеть, как я понял?

Кликните здесь для просмотра всего текста

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 · 01.08.2013, 11:21

Сообщение от salam

массивчик такой нужно посчитать.

по нему легко восстановить, сколько и чего было в исходном массиве.

Добавлено через 1 минуту
но это, конечно, если речь идет о быстром решении. то, о чем я говорил работает за O(N). однако есть совсем простой способ с std::map. он будет стоить вам O(n*logn).

Tulosba · 01.08.2013, 11:21

Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано)
1,1,2,2 -> должен вернуть 2?
1,1,1,2 -> должен вернуть 3?

@salam · 01.08.2013, 11:25

Сообщение от Maxak

Реализация так вот будет выглядеть, как я понял?

да. очевидно, он тоже линеен. при том без доп. памяти.

Добавлено через 1 минуту
только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.

@Maxak · 01.08.2013, 11:35 **[ТС]**

Сообщение от Tulosba

Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано)

ага, спасибо.

Сообщение от Tulosba

Maxak, 1,1,2,2 -> должен вернуть 2?
1,1,1,2 -> должен вернуть 3?

Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".

Добавлено через 1 минуту

Сообщение от salam

только ваш алгоритм считает количество в массиве непонятных объектов "дубликат". практически полезно иметь информацию о том, чего сколько.

Да, может вы и правы сейчас пересмотрю общую задачу. Может я не правильно сделал декомпозицию задачи.

Tulosba · 01.08.2013, 12:24

Сообщение от Maxak

Да верно. Т.е. мне нужно посчитать количество уникальных значений. Которое равно размерность минус "мои дубликаты".

Что-то я уже не уверен, что "1,1,1,2" должно вернуть "3"

Есть наиболее полная формулировка задачи?

@salam · 01.08.2013, 13:08

дело в том, что массивчик ans[] решает более общую задачу. имея его, вы можете сказать, каких сколько и сколько уникальных тоже.

@Maxak · 01.08.2013, 13:13 **[ТС]**

обобщил задачу
Выделить из упорядоченного массива подмассив ограниченный точками x1, x2

@iel · 01.08.2013, 13:40

Это ещё что за нафиг?

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++;
    }

И будет вам количество дубликатов.

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	01.08.2013, 10:56
	у вас верхняя оценка квадратичная. легко считается за линию. т.к. массив упорядочен, одинаковые стоят рядом. тогда для a_i ответом будет: (a[i] == a[i-1] ? ans[i-1] + 1 : 0). 1

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	01.08.2013, 10:58
	std::equal_range + std::distance, или, тупо, std::count (но тогда придется весь массив пробежать) 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	01.08.2013, 11:15
	ans_i - количество элементов, равных a_i, не считая его самого. массивчик такой нужно посчитать. 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	01.08.2013, 11:21
	Maxak, какие-то странные у Вас дубликаты. (и условие в 6 строке напутано) 1,1,2,2 -> должен вернуть 2? 1,1,1,2 -> должен вернуть 3? 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	01.08.2013, 13:08
	дело в том, что массивчик ans[] решает более общую задачу. имея его, вы можете сказать, каких сколько и сколько уникальных тоже. 0

@Maxak 0 / 0 / 1 Регистрация: 27.12.2012 Сообщений: 47
	01.08.2013, 13:13 [ТС]
	обобщил задачу Выделить из упорядоченного массива подмассив ограниченный точками x1, x2 0