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

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

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

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

11.01.2014, 20:14. Просмотров 1166. Ответов 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();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.01.2014, 20:14     Самый редко встречающийся элемент в массиве
Посмотрите здесь:

Самый редко встречаемый символ C++
C++ Самый часто встречаемый символ в массиве
Самый самый самый простой пример рекурсии C++
C++ Найти самый большой элемент Массива
C++ наименьший, самый редкий элемент из массива чисел
C++ Определить, какой символ наиболее редко встречается в заданном массиве(шаблоны)
Найти самый наименьший элемент в матрице, и найти сумму столбца который стоит этот наименьший найденный элемент C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
22148 / 10622 / 1729
Регистрация: 12.02.2012
Сообщений: 17,667
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;
}
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 115
11.01.2014, 20:37  [ТС]     Самый редко встречающийся элемент в массиве #3
Извиняюсь за наглость а моно с коментариями.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
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))
Catstail
Модератор
22148 / 10622 / 1729
Регистрация: 12.02.2012
Сообщений: 17,667
11.01.2014, 22:00     Самый редко встречающийся элемент в массиве #5
Цитата Сообщение от outoftime Посмотреть сообщение
Зато сложность O(2*n*log(n))
- а у меня O(n)
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 22:26     Самый редко встречающийся элемент в массиве #6
Catstail, допустим на максимальный расширить легко, но у вас работа на алфавите 256 значений, а у меня на любом массиве данных поддерживающих оператор сравнения operator<(T, T).
Catstail
Модератор
22148 / 10622 / 1729
Регистрация: 12.02.2012
Сообщений: 17,667
11.01.2014, 22:38     Самый редко встречающийся элемент в массиве #7
outoftime, так в коде ТС речь шла о массиве char-ов. Это сильно упрощает задачу.
Tulosba
:)
Эксперт С++
4387 / 3230 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.01.2014, 23:24     Самый редко встречающийся элемент в массиве #8
Цитата Сообщение от Catstail Посмотреть сообщение
а у меня O(n)
Благодаря строке 10 она у Вас как минимум квадратичная.
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};
Dani
1264 / 622 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
11.01.2014, 23:36     Самый редко встречающийся элемент в массиве #10
Цитата Сообщение от Tulosba Посмотреть сообщение
Благодаря строке 10 она у Вас как минимум квадратичная.
O(n) же получается. Откуда квадрат?
Цитата Сообщение от outoftime Посмотреть сообщение
Зато сложность O(2*n*log(n))
2 не учитывается, т.к. это скрытая константа. Итого: O(n*log(n))
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;}
посмотрите на результат.
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 23:40     Самый редко встречающийся элемент в массиве #12
Tulosba, не, нету там никаких квадратов, там реально O(n)+const, просто форматирование ужасное можно потеряться.
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 115
11.01.2014, 23:40  [ТС]     Самый редко встречающийся элемент в массиве #13
Спасибо братцы.
Но я в программирование далеко не гений, нельзя ли подробнее. Чего и в какой последовательности?
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 23:43     Самый редко встречающийся элемент в массиве #14
Цитата Сообщение от Dani Посмотреть сообщение
2 не учитывается, т.к. это скрытая константа
Просто не знаю как сигму ставить.

Добавлено через 1 минуту
koto_fey, кури код с поста 2, когда вкуришь смотри код с поста 4
Tulosba
:)
Эксперт С++
4387 / 3230 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.01.2014, 23:44     Самый редко встречающийся элемент в массиве #15
Цитата Сообщение от Dani Посмотреть сообщение
Откуда квадрат?
Оттуда, что на каждой итерации цикла (которых strlen) считается эта самая strlen(), которая линейно зависит от n.
xoror
29 / 31 / 2
Регистрация: 15.12.2013
Сообщений: 147
11.01.2014, 23:44     Самый редко встречающийся элемент в массиве #16
Цитата Сообщение от Ev_Hyper Посмотреть сообщение
for (i=0; i<256; i++){cout<<Freq[i]<<" "; Freq[i]=0; cout<<Freq[i]<<endl;}
отличается от этого
Цитата Сообщение от Catstail Посмотреть сообщение
C++
1
2
3
4
5
6
void PrintRare(char *s) 
{ 
   unsigned int i,min,Freq[256]; 
   char q; 
   
   for (i=0; i<256; i++) Freq[i]=0;
В цикле идет только обнуление всех элементов массива. 256 итераций!

Массив можно обнулить при его инициализации
C++
1
unsigned int Freq[256] = {0};
koto_fey
5 / 5 / 1
Регистрация: 11.01.2013
Сообщений: 115
11.01.2014, 23:45  [ТС]     Самый редко встречающийся элемент в массиве #17
Содержательный ответ.
Ev_Hyper
11.01.2014, 23:49
  #18

Не по теме:

xoror, не сразу понял о чем ты

outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.01.2014, 00:15     Самый редко встречающийся элемент в массиве #19
Tulosba, действительно квадрат, но это больше вопрос оптимизации нежели сложности самого алгоритма, так что терпимо (:
koto_fey,
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 <iostream>
#include <algorithm>
#include <iterator>
#include <cstring>
 
void PrintRare(const char *str)
{
    const int n = 256;
    std::size_t frequency[n] = {0},
                strlen       = std::strlen(str);
 
    for (int i = 0; i < strlen; ++frequency[str[i++]]);
 
    std::size_t max = *std::max_element(std::begin(frequency), std::end(frequency)),
                min = max;
    for (int i = 0; i < n; ++i)
    {
        if (frequency[i])
        {
            min = std::min(min, frequency[i]);
        }
    }
 
    for (const std::size_t &count : {min, max})
    {
        for (int i = 0; i < n; ++i)
        {
            if (frequency[i] == count)
                std::cout << char(i) << " ";
        }
        std::cout << std::endl;
    }
}
 
int main(int argc, char* argv[])
{
    char *S = "aasaassgkldfkeej";
    PrintRare(S);
    return 0;
}
Это типа средней сложности (я о сложности кода). Кто знает как можно найти минимум используя библиотечные функции? Просто там надо отфильтровывать все нули, в общем то в этим у меня и возникла проблема.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2014, 00:17     Самый редко встречающийся элемент в массиве
Еще ссылки по теме:

C++ Найти второй самый большой элемент массива и второй самый маленький элемент массива
C++ Определить чаще всего встречающийся элемент массива
Найти чаще всего встречающийся элемент массива C++
C++ Найти самый часто встречающийся символ в тексте
Найти самый большой положительный элемент заданного массива C++

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4387 / 3230 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
12.01.2014, 00:17     Самый редко встречающийся элемент в массиве #20
Цитата Сообщение от outoftime Посмотреть сообщение
Кто знает как можно найти минимум используя библиотечные функции?
минимум чего?
Yandex
Объявления
12.01.2014, 00:17     Самый редко встречающийся элемент в массиве
Ответ Создать тему
Опции темы

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