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

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

Войти
Регистрация
Восстановить пароль
 
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
#1

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

13.06.2014, 23:12. Просмотров 1098. Ответов 5
Метки нет (Все метки)

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

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

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

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

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

Классы. В массиве чисел размером 6х6 элементов найти максимальный элемент, минимальный элемент и их индексы - C++
В массиве чисел размером 6х6 элементов найти максимальный элемент, минимальный элемент и их индексы. ...

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

5
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 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;
}
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
14.06.2014, 13:50  [ТС] #3
RaiaNKnight, В том то и дело, что сортировать не нужно. Я должен ввести, допустим, так:
7
2 3 2 4 1 3 1
и мне должно вывести 1. А выведет в этом случае 2, то есть первый встречный элемент, повторяющийся максимальное количество раз в массиве. Не понимаю, как минимум без сортировки найти.
0
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
14.06.2014, 15:06 #4
Вы код пробовали компилить и запускать? Единицу выдаёт, всё как вам надо.

Причём если не сортировать, то сложность прямого решения - это O(N^2), а я вам предлагаю O(N*log(N)).
1
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 676
14.06.2014, 15:09  [ТС] #5
RaiaNKnight, Спасибо вам.
0
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
14.06.2014, 15:13 #6
Без сортировки вот так:
1) Пусть максимальная частота среди элементов равна 1 (т.е. пока мы не знаем, какой элемент встречается чаще всего);
2) Пусть минимум (который вам нужно вывести) равен минимальному среди чисел в вашем массиве (просто нашли предварительно минимум и запомнили его в какой-либо переменной;
3) Для каждого элемента считаете сколько он раз встречается в массиве.
4) Сравниваете это число с максимальной частотой и текущим "минимумом"
5) Если текущая максимальная частота больше известно, то запоминаете текущую максимальную частоту и элемент массива, для которого вы её считали
6) После того, как проделаете такую процедуру для всех элементов массива, выведете максимальную частоту и "минимум". Это и будет решением вашей задачи.
1
14.06.2014, 15:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.06.2014, 15:13
Привет! Вот еще темы с ответами:

Цифра, повторяющаяся максимальное количество раз - C++
Добрый день. Вообщем нужна помощь в исправлении программы. На данный момент программа считает количество максимально повторившегося...

Дан массив целых чисел. Найти В этом массиве минимальный элемент т и максимальный элемент м. Вывести сумму элементов от минимального до максимального - C++
Дан массив целых чисел. Найти В этом массиве минимальный элемент т и максимальный элемент м. Вывести сумму элементов от минимального до...

Найти число, повторяющееся максимальное количество раз - C++
Прошу помощи. Болел - ничего не понял. Скоро экзамен, а я ничего не понимаю в С++. Дали примерные задачи, а я не понимаю как решать. Вот...

В целочисленной матрице определить элемент, который повторяется максимальное число раз - C++
Задача. В целочисленной матрице А определить элемент, который повторяется максимальное число раз. Получить матрицу B умножением матрицы А...


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

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

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