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

Минимальный элемент, повторяющийся максимальное количество раз в массиве - C++

Восстановить пароль Регистрация
 
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
13.06.2014, 23:12     Минимальный элемент, повторяющийся максимальное количество раз в массиве #1
Привет всем. Мне нужно вывести минимальный элемент, повторяющийся максимальное количество раз в массиве. С поиском элемента, повторяющегося максимальное количество раз проблем не возникло. А вот со второй частью задания возникли проблемы. Вот мой код.
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
#include <iostream>
#include <conio.h>
using namespace std;
 
int a[100000];
 
int main()
{
    int n, i, j;
    cin >> n;
 
    for(i = 0;i < n;i++)
        cin >> a[i];
 
    int max = 0, num = 0;
    for(i = 0;i < n;i++){
        int count = 0;
        for(j = i;j < n;j++)
            if(a[i] == a[j])
                count++;
        if(max < count){
            max = count;
            num = i;
        }
    }
    int min = a[num];
    for(i = num;i < n;i++){
        if(a[i] <= min)
            min = a[i];
    }
    cout << min << " ";
 
    getch();
 
    return 0;
}
Я здесь намудрил вот с этим.
C++
1
2
3
4
5
int min = a[num];
    for(i = num;i < n;i++){
        if(a[i] <= min)
            min = a[i];
    }
Не могу понять, как цикл подправить.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.06.2014, 23:12     Минимальный элемент, повторяющийся максимальное количество раз в массиве
Посмотрите здесь:

C++ В целочисленной матрице определить элемент, который повторяется максимальное число раз
C++ Цифра, повторяющаяся максимальное количество раз
C++ Найти в массиве максимальный и минимальный элементы в массиве и их количество
Дан массив целых чисел. Найти В этом массиве минимальный элемент т и максимальный элемент м. Вывести сумму элементов от минимального до максимального C++
C++ Классы. В массиве чисел размером 6х6 элементов найти максимальный элемент, минимальный элемент и их индексы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
14.06.2014, 09:18     Минимальный элемент, повторяющийся максимальное количество раз в массиве #2
Если если возможность использовать сортировку, то алгоритм такой:
1) Отсортируем массив по возрастанию;
2) Ищем максимальное количество идущих подряд одинаковых элементов, двигаясь слева направо

Причём когда сравниваете размер текущее максимальное количество с найденным, используете знак строго больше '>'. Примерный код:

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
#include <algorithm>
#include <iostream>
using namespace std;
 
int main() {
    int a[10000];
    int n;
    
    cin >> n;
    for( int i = 0; i < n; ++i ) {
        cin >> a[i];
    }
    
    sort(a, a+n);
    int aMin = a[0];
    
    int maxRepeat = 1;
    int maxValue = aMin;
    
    int currRepeat = 1;
    int currValue = 0;
 
    for( int i = 1; i < n; ++i ) {
        if( a[i] == a[i-1] ) {
            currValue = a[i];
            ++currRepeat;
        } else {
            currRepeat = 1;
        }
        
        if( currRepeat > maxRepeat ) {
            maxRepeat = currRepeat;
            maxValue = currValue;
        }
    }    
 
    cout << maxValue << endl;
 
    return 0;
}
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
14.06.2014, 13:50  [ТС]     Минимальный элемент, повторяющийся максимальное количество раз в массиве #3
RaiaNKnight, В том то и дело, что сортировать не нужно. Я должен ввести, допустим, так:
7
2 3 2 4 1 3 1
и мне должно вывести 1. А выведет в этом случае 2, то есть первый встречный элемент, повторяющийся максимальное количество раз в массиве. Не понимаю, как минимум без сортировки найти.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
14.06.2014, 15:06     Минимальный элемент, повторяющийся максимальное количество раз в массиве #4
Вы код пробовали компилить и запускать? Единицу выдаёт, всё как вам надо.

Причём если не сортировать, то сложность прямого решения - это O(N^2), а я вам предлагаю O(N*log(N)).
Sh@dow777
11 / 11 / 3
Регистрация: 10.12.2013
Сообщений: 645
14.06.2014, 15:09  [ТС]     Минимальный элемент, повторяющийся максимальное количество раз в массиве #5
RaiaNKnight, Спасибо вам.
RaiaNKnight
 Аватар для RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 458
Записей в блоге: 1
14.06.2014, 15:13     Минимальный элемент, повторяющийся максимальное количество раз в массиве #6
Без сортировки вот так:
1) Пусть максимальная частота среди элементов равна 1 (т.е. пока мы не знаем, какой элемент встречается чаще всего);
2) Пусть минимум (который вам нужно вывести) равен минимальному среди чисел в вашем массиве (просто нашли предварительно минимум и запомнили его в какой-либо переменной;
3) Для каждого элемента считаете сколько он раз встречается в массиве.
4) Сравниваете это число с максимальной частотой и текущим "минимумом"
5) Если текущая максимальная частота больше известно, то запоминаете текущую максимальную частоту и элемент массива, для которого вы её считали
6) После того, как проделаете такую процедуру для всех элементов массива, выведете максимальную частоту и "минимум". Это и будет решением вашей задачи.
Yandex
Объявления
14.06.2014, 15:13     Минимальный элемент, повторяющийся максимальное количество раз в массиве
Ответ Создать тему
Опции темы

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