Нахождение нескольких, наиболее часто встречаемых элементов массива

@Занзибар · Регистрация: 02.01.2015

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

Добрый вечер. Всех с наступившим новым годом! Есть вот такая вот задача -
Необходимо найти моду(наиболее часто встречаемый элемент массива). При учете, что их может быть несколько.
Например:
{ 2,5,3,7,0,9,9,0}
мода = 0 и 9
встречаются = 2 и 2 раза.

Вот этот код -

C#
1
2
3
4
5
6
7
8
9
10
11
12
  
 int max = a[0], cmax = 0, rmax = 0;
    for (int i = 0; i < N; i++) {
        if (cmax > rmax) {
            rmax = cmax;            
            max = a[i - 1];    
        }
        cmax = 0;
        for (int j = i; j < N; j++)
           if (a[j] == a[i])
              cmax++;
    }

определяет только первую моду(0). Как найти все моды массива?
Спасибо за помощь.

@ltkj · 02.01.2015, 14:49

Сообщение от Занзибар

Добрый вечер. Всех с наступившим новым годом! Есть вот такая вот задача -
Необходимо найти моду(наиболее часто встречаемый элемент массива). При учете, что их может быть несколько.
Например:
{ 2,5,3,7,0,9,9,0}
мода = 0 и 9
встречаются = 2 и 2 раза.

Вот этот код -

C#
1
2
3
4
5
6
7
8
9
10
11
12
  
 int max = a[0], cmax = 0, rmax = 0;
    for (int i = 0; i < N; i++) {
        if (cmax > rmax) {
            rmax = cmax;            
            max = a[i - 1];    
        }
        cmax = 0;
        for (int j = i; j < N; j++)
           if (a[j] == a[i])
              cmax++;
    }

определяет только первую моду(0). Как найти все моды массива?
Спасибо за помощь.

Ограничения есть какие-нибудь? Если нет, то можно тупо ввести второй массив d[i] - кол-во элементов, совпадающих с a[i]( и лежащих не левее во избежание повторений при выводе). Потом найти максимум у d[i], а потом вывести все a[i], где d[i] = max.
Если память нельзя выделять, то могу ниже описать и другой алгоритм.
Для начала просто вычислите rmax, что вы и сделали. Далее повторить то же самое, только в случае cmax == rmax вывести a[i]. И if надо ниже опустить - после подсчёта cmax проверять надо

@Catstail · 02.01.2015, 15:01

Подозреваю, что твой код совсем на другую тему. Вот рабочий код:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
void printModa(int *A, int n)
{
     int *B,*C;
     int i,j,p,q,m;
     B=(int *)calloc(1,n);
     C=(int *)calloc(1,n);
     p=0;
     for (i=0; i<n; i++)
     {
         q=0;
         for (j=0; j<p; j++)
             if (A[i]==B[j])
             {
                 C[j]++;
                 q=-1;
                 break;
             }           
         if (q==0)
         {
           B[p]=A[i];
           C[p]=1;
           p++;
         }
      }
      m=C[0];
      for (i=1; i<p; i++)
          if (C[i]>m) m=C[i];
      for (i=0; i<p; i++)
        if (C[i]==m) printf("%d ",B[i]);
      printf("\n");
      free(B);
      free(C);
}      
 
int main(int argc, char *argv[])
{
  int Arr[]={2,5,3,7,0,9,9,0};
  
  printModa(Arr,sizeof(Arr)/sizeof(int)); 
  
  system("PAUSE");  
  return 0;
}

@ltkj · 02.01.2015, 15:22

Да нет, там код вроде в тему. Вот примерный переделанный ваш алгоритм, не использующий доп памяти:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int cmax = 0, rmax = 0;
    for (int i = 0; i < N; i++) {
        cmax = 0;
        for (int j = i; j < N; j++) {
           if (a[j] == a[i]) {
              cmax++;
           }
        }
        if (cmax > rmax) {
            rmax = cmax;             
        } 
    }
    // выше нашли популярность самого популярного элемента.
 
    for (int i = 0; i < N; i++) {
        cmax = 0;
        for (int j = i; j < N; j++) {
           if (a[j] == a[i]) {
              cmax++;
           }
        }
        if (cmax == rmax) {
        // если популярность текущего элемента равна максимальной популярности, то его надо вывести
            printf("%d\n", a[i]);      
        } 
    }

@Catstail · 02.01.2015, 15:38

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

не использующий доп памяти:

- но работающий вдвое медленнее...

@ltkj · 02.01.2015, 15:44

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

- но работающий вдвое медленнее...

Если уж говорить о скорости, то в обоих случаях она O(n^2). Зачем заботиться о константе, если есть алгоритм, работающий за O(n log n)? Для этого сначала отсортировать массив, а уже последующие действия будут линейными по сложности. Тут явно суть не в скорости. Ну чисто имхо, я тут гнался ещё за пониманием автора, а нечто похожее автор темы уже писал.

А задача похожа на какую-нибудь университетскую - у нас часто были ограничения на память, потому и написал решение с учётом этого.

@Catstail · 02.01.2015, 15:51

ltkj, да оба алгоритма O(n²), но Ваш дважды крутит два вложенных цикла... Конечно, сортировка (быстрая) здесь помогла бы.

@ltkj · 02.01.2015, 16:04

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

ltkj, да оба алгоритма O(n²), но Ваш дважды крутит два вложенных цикла... Конечно, сортировка (быстрая) здесь помогла бы.

Давайте я иначе сформулирую вопрос: в чем преимущества вашего алгоритма и какие вы видите основные критерии сравнивания алгоритмов?
Если преимущество только в скорости (хотя полагаю, что скорость автора не заботит) и это единственный критерий, то существует решение намного лучше. Лучше тогда его написать.
У моего же решения 2 цели: его простота понимания (оно как бы продолжает логику автора, а не решает задачу заново) и отсутсвие лишней памяти, про которую я писал выше.

P.s. если бы не было условия на доп память, то можно просто запонимать cmax в первом цикле, было бы примерно как у вас по сложности, только чуть проще (опять же, имхо).

@Catstail · 02.01.2015, 17:16

ltkj, соглашусь. Ваш алгоритм проще. Мой делает лишнее - считает частоты всех элементов.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	02.01.2015, 15:51
	ltkj, да оба алгоритма O(n²), но Ваш дважды крутит два вложенных цикла... Конечно, сортировка (быстрая) здесь помогла бы. 0

@Catstail Супер-модератор 38178 / 21113 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	02.01.2015, 17:16
	ltkj, соглашусь. Ваш алгоритм проще. Мой делает лишнее - считает частоты всех элементов. 0