С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 116
#1

Самый редко встречающийся элемент в массиве - C++

11.01.2014, 20:14. Просмотров 1322. Ответов 37
Метки нет (Все метки)

Всех приветствую!
Прошу помощи. Собственно идея задачи вроде бы проста нужно найти самый часто и редко встречающийся эллемент в массиве.

Вот я написал для поиска частого элемента и поиска редкого, загвостка в том что он выводит только одно вхождение, т.е. если несколько элементов встречаются одинаковое колличества раз, то он выводит только последние увиденные.
вот код, для вывода редко встречающегося ээлемента. Как сделать что бы он все выводил а не один.
Точнее куда запендюрить вывод. Вставляя в циклы он мне всякую ерись выдает. (код написан на MVS 2010)
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
void main(void)
{   int n;
    cin>>n;
    char *m=new char[n];
 
    for (int i=0;i<n; i++)
    {
      //m[i]=rand()%100;
        cin>>m[i];
 
    //  cout<<" "<<m[i];
    }
       int k=0,k1=0,kmax,kmin;int i=0,j,fi,fj=0;
      
       while(i<n)
       {
           kmax=0;
 
           for(j=i+1;j<n;j++)   
         {
             
             if(m[j]!=m[i])         
             { 
 
                 k++;
                 fi=j;       
             
             }  
            
         }
           
        i++;
        
      
       }
     
      cout<<" "<<m[fi]; 
       delete m;
        _getch();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.01.2014, 20:14
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Самый редко встречающийся элемент в массиве (C++):

Самый редко встречаемый символ - C++
Задан массив A. Найти самый редко встречаемый символ. Может быть пригодится кому, но вот исходник задачи обратной - самый часто...

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

Найти в массиве элемент, самый близкий по величине к заданному числу - C++
Напишите программу, которая находит в массиве элемент, самый близкий по величине к данному числу. С++ Входные данные В первой...

Вывести те числа, которые наиболее редко встречаются в массиве и количество их повторений - C++
Дан одномерный массив из 150 случайных целых чисел в диапазоне от 14 до 37 включительно. Вывести те числа, которые наиболее редко...

Определить, какой символ наиболее редко встречается в заданном массиве(шаблоны) - C++
Доброго времени суток, товарищи эксперты! Написал программу по следующему заданию: Задан массив int A, элементы которого могут быть...

Найти второй самый большой элемент массива и второй самый маленький элемент массива - C++
Помогите пожалуйста: Найти второй самый большой элемент массива и второй самый маленький элемент массива.

37
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
11.01.2014, 20:26 #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
#include <iostream.h>
#include <string.h>
 
void PrintRare(char *s)
{
    unsigned int i,min,Freq[256];
    char q;
 
    for (i=0; i<256; i++) Freq[i]=0;
    for (i=0; i<strlen(s); i++)
    {
        q=s[i];
        Freq[q]++;
    }
 
    min=strlen(s);
    for (i=0; i<256; i++)
        if ((Freq[i] > 0) && (Freq[i] < min)) min=Freq[i];
 
    for (i=0; i<256; i++)
        if (Freq[i] == min)
        {
            q=i;
            cout << q << endl;
        }
}
 
int main(int argc, char* argv[])
{
    char *S="aasaassgkldfkeej";
    PrintRare(S);
    return 0;
}
0
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 116
11.01.2014, 20:37  [ТС] #3
Извиняюсь за наглость а моно с коментариями.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2014, 21:32 #4
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 <vector>
#include <map>
 
template<typename _Type, std::size_t _N>
auto minmax(const _Type (&array)[_N])
{
    std::map<_Type, int> couter;
    for (const _Type &elem : array)
        ++couter[elem];
 
    std::multimap<int, _Type> frequency;
    for (const auto &pair : couter)
        frequency.insert({pair.second, pair.first});
 
    std::vector<_Type> min, max;
    for (auto it = frequency.begin(); it != frequency.end()
        && it->first == frequency.begin()->first; ++it)
        min.push_back(it->second);
    for (auto it = frequency.rbegin(); it != frequency.rend()
        && it->first == frequency.rbegin()->first; ++it)
        max.push_back(it->second);
 
    return std::make_pair(min, max);
}
 
int main()
{
    int array[] = {1,2,3,4,5,6,7,3,77,2,4,2,6,2,33,5,6,2,3};
    auto res = minmax(array);
    for (const int &min : res.first)
        std::cout << min << " ";
    std::cout << std::endl;
    for (const int &max : res.second)
        std::cout << max << " ";
}
koto_fey, Жесть, думал будет меньше...

Добавлено через 25 минут
Зато сложность O(2*n*log(n))
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
11.01.2014, 22:00 #5
Цитата Сообщение от outoftime Посмотреть сообщение
Зато сложность O(2*n*log(n))
- а у меня O(n)
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2014, 22:26 #6
Catstail, допустим на максимальный расширить легко, но у вас работа на алфавите 256 значений, а у меня на любом массиве данных поддерживающих оператор сравнения operator<(T, T).
0
Catstail
Модератор
22915 / 11281 / 1833
Регистрация: 12.02.2012
Сообщений: 18,492
11.01.2014, 22:38 #7
outoftime, так в коде ТС речь шла о массиве char-ов. Это сильно упрощает задачу.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
11.01.2014, 23:24 #8
Цитата Сообщение от Catstail Посмотреть сообщение
а у меня O(n)
Благодаря строке 10 она у Вас как минимум квадратичная.
0
xoror
29 / 31 / 2
Регистрация: 15.12.2013
Сообщений: 147
11.01.2014, 23:30 #9
Цитата Сообщение от Tulosba Посмотреть сообщение
Благодаря строке 10 она у Вас как минимум квадратичная.
В 9 строке тоже выполняется ненужная работа
C++
1
2
3
for (i=0; i<256; i++) Freq[i]=0;
               ||
unsigned int Freq[256] = {0};
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,295
Записей в блоге: 2
Завершенные тесты: 1
11.01.2014, 23:36 #10
Цитата Сообщение от Tulosba Посмотреть сообщение
Благодаря строке 10 она у Вас как минимум квадратичная.
O(n) же получается. Откуда квадрат?
Цитата Сообщение от outoftime Посмотреть сообщение
Зато сложность O(2*n*log(n))
2 не учитывается, т.к. это скрытая константа. Итого: O(n*log(n))
0
Ev_Hyper
Заблокирован
11.01.2014, 23:39 #11
Цитата Сообщение от xoror Посмотреть сообщение
В 9 строке тоже выполняется ненужная работа
уверены?
C++
1
for (i=0; i<256; i++){cout<<Freq[i]<<" "; Freq[i]=0; cout<<Freq[i]<<endl;}
посмотрите на результат.
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2014, 23:40 #12
Tulosba, не, нету там никаких квадратов, там реально O(n)+const, просто форматирование ужасное можно потеряться.
0
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 116
11.01.2014, 23:40  [ТС] #13
Спасибо братцы.
Но я в программирование далеко не гений, нельзя ли подробнее. Чего и в какой последовательности?
0
outoftime
║XLR8║
511 / 433 / 33
Регистрация: 25.07.2009
Сообщений: 2,295
11.01.2014, 23:43 #14
Цитата Сообщение от Dani Посмотреть сообщение
2 не учитывается, т.к. это скрытая константа
Просто не знаю как сигму ставить.

Добавлено через 1 минуту
koto_fey, кури код с поста 2, когда вкуришь смотри код с поста 4
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
11.01.2014, 23:44 #15
Цитата Сообщение от Dani Посмотреть сообщение
Откуда квадрат?
Оттуда, что на каждой итерации цикла (которых strlen) считается эта самая strlen(), которая линейно зависит от n.
2
11.01.2014, 23:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.01.2014, 23:44
Привет! Вот еще темы с ответами:

Найти чаще всего встречающийся элемент массива - C++
#include &lt;iostream&gt; using namespace std; int main(void) { const int n=10; int a = { 1,2,0,1,2,1,3,3,4,2 }; int k,l,max; ...

Определить чаще всего встречающийся элемент массива - C++
Определить чаще всего встречающийся элемент массива А. Добавлено через 6 минут P.S. желательно использовать комментарии в коде=)...

Самый самый самый простой пример рекурсии - C++
приведите самый прост пример рекурсии)))void main(int k) { int n=10; k=n; k++; n=k; if(n!=20)main(n); ...

Самый часто встречаемый символ в массиве - C++
А как можно найти наиболее часто встречающийся символ в массиве из х элементов


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

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

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