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

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

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

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

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

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

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

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

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

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

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

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

Причём если не сортировать, то сложность прямого решения - это O(N^2), а я вам предлагаю O(N*log(N)).
Sh@dow777
12 / 12 / 3
Регистрация: 10.12.2013
Сообщений: 664
14.06.2014, 15:09  [ТС]     Минимальный элемент, повторяющийся максимальное количество раз в массиве #5
RaiaNKnight, Спасибо вам.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.06.2014, 15:13     Минимальный элемент, повторяющийся максимальное количество раз в массиве
Еще ссылки по теме:

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

дана матрица А(5,5). Каждый минимальный элемент строки поменять на максимальное значение элемента, побочной диагонали - C++
дана матрица А(5,5). Каждый минимальный элемент строки поменять на максимальное значение элемента, побочной диагонали.

Удалить из текста слова которые встречается максимальное количество раз - C++
Пусть задано множество строк в файле. Отредактировать текст, удалив из него то слово (те слова) которое встречается максимальное количество...

Найти минимальный элемент в массиве - C++
Найти минимальный элемент в массиве A и обнулить все элементы , стоящие в массиве после него. Решить задачу , используя указатели. ...

Найти минимальный элемент в массиве - C++
Составьте программу используя двумерный массив. Размеры массива задайте сами. Сделать три варианта программы. В первом элементы массива...

Найти минимальный элемент в массиве - C++
Найти минимальный элемент в массиве


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

Или воспользуйтесь поиском по форуму:
RaiaNKnight
96 / 70 / 7
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
14.06.2014, 15:13     Минимальный элемент, повторяющийся максимальное количество раз в массиве #6
Без сортировки вот так:
1) Пусть максимальная частота среди элементов равна 1 (т.е. пока мы не знаем, какой элемент встречается чаще всего);
2) Пусть минимум (который вам нужно вывести) равен минимальному среди чисел в вашем массиве (просто нашли предварительно минимум и запомнили его в какой-либо переменной;
3) Для каждого элемента считаете сколько он раз встречается в массиве.
4) Сравниваете это число с максимальной частотой и текущим "минимумом"
5) Если текущая максимальная частота больше известно, то запоминаете текущую максимальную частоту и элемент массива, для которого вы её считали
6) После того, как проделаете такую процедуру для всех элементов массива, выведете максимальную частоту и "минимум". Это и будет решением вашей задачи.
Yandex
Объявления
14.06.2014, 15:13     Минимальный элемент, повторяющийся максимальное количество раз в массиве
Ответ Создать тему
Опции темы

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