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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
koto_fey
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 93
11.01.2014, 20:14     Самый редко встречающийся элемент в массиве #1
Всех приветствую!
Прошу помощи. Собственно идея задачи вроде бы проста нужно найти самый часто и редко встречающийся эллемент в массиве.

Вот я написал для поиска частого элемента и поиска редкого, загвостка в том что он выводит только одно вхождение, т.е. если несколько элементов встречаются одинаковое колличества раз, то он выводит только последние увиденные.
вот код, для вывода редко встречающегося ээлемента. Как сделать что бы он все выводил а не один.
Точнее куда запендюрить вывод. Вставляя в циклы он мне всякую ерись выдает. (код написан на 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();
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
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
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 93
11.01.2014, 20:37  [ТС]     Самый редко встречающийся элемент в массиве #3
Извиняюсь за наглость а моно с коментариями.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 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
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
11.01.2014, 22:00     Самый редко встречающийся элемент в массиве #5
Цитата Сообщение от outoftime Посмотреть сообщение
Зато сложность O(2*n*log(n))
- а у меня O(n)
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 22:26     Самый редко встречающийся элемент в массиве #6
Catstail, допустим на максимальный расширить легко, но у вас работа на алфавите 256 значений, а у меня на любом массиве данных поддерживающих оператор сравнения operator<(T, T).
Catstail
Модератор
 Аватар для Catstail
21434 / 10219 / 1666
Регистрация: 12.02.2012
Сообщений: 17,092
11.01.2014, 22:38     Самый редко встречающийся элемент в массиве #7
outoftime, так в коде ТС речь шла о массиве char-ов. Это сильно упрощает задачу.
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.01.2014, 23:24     Самый редко встречающийся элемент в массиве #8
Цитата Сообщение от Catstail Посмотреть сообщение
а у меня O(n)
Благодаря строке 10 она у Вас как минимум квадратичная.
xoror
 Аватар для 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
1263 / 621 / 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
 Аватар для Ev_Hyper
1805 / 1626 / 435
Регистрация: 15.12.2013
Сообщений: 5,773
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║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 23:40     Самый редко встречающийся элемент в массиве #12
Tulosba, не, нету там никаких квадратов, там реально O(n)+const, просто форматирование ужасное можно потеряться.
koto_fey
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 93
11.01.2014, 23:40  [ТС]     Самый редко встречающийся элемент в массиве #13
Спасибо братцы.
Но я в программирование далеко не гений, нельзя ли подробнее. Чего и в какой последовательности?
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2014, 23:43     Самый редко встречающийся элемент в массиве #14
Цитата Сообщение от Dani Посмотреть сообщение
2 не учитывается, т.к. это скрытая константа
Просто не знаю как сигму ставить.

Добавлено через 1 минуту
koto_fey, кури код с поста 2, когда вкуришь смотри код с поста 4
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.01.2014, 23:44     Самый редко встречающийся элемент в массиве #15
Цитата Сообщение от Dani Посмотреть сообщение
Откуда квадрат?
Оттуда, что на каждой итерации цикла (которых strlen) считается эта самая strlen(), которая линейно зависит от n.
xoror
 Аватар для 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
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 93
11.01.2014, 23:45  [ТС]     Самый редко встречающийся элемент в массиве #17
Содержательный ответ.
Ev_Hyper
11.01.2014, 23:49
  #18

Не по теме:

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

outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 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++

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

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

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