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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
koto_fey
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 90
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();
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.01.2014, 00:29     Самый редко встречающийся элемент в массиве #21
Цитата Сообщение от Tulosba Посмотреть сообщение
минимум чего?
По коду выше, пытаюсь найти минимальный натуральный элемент массива (т.е. больше нуля). Можно было-бы через std::for_each пройтись, но там лямбду надо да и опять тоже сравнение будет, хотелось бы что-бы std::min_element как то не брал во внимание нулевые значения.

Добавлено через 1 минуту
koto_fey, п.с. надо добавить еще выход при пустой строке (:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,398
12.01.2014, 00:34     Самый редко встречающийся элемент в массиве #22
Цитата Сообщение от xoror Посмотреть сообщение
unsigned Freq[256] = {0};
C++
1
unsigned Freq[256] = {};
тоже покатит
Tulosba
:)
Эксперт C++
4377 / 3220 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
12.01.2014, 00:51     Самый редко встречающийся элемент в массиве #23
Цитата Сообщение от MrGluck Посмотреть сообщение
C++
1
unsigned Freq[256] = {};
тоже покатит
Плохо только, что:
- unsigned;
- опущен int;
- размер захардкожен.

Цитата Сообщение от outoftime Посмотреть сообщение
не брал во внимание нулевые значения.
Тут уж, либо свой предикат, либо удалить неугодные элементы перед поиском. Третьего не дано.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.01.2014, 01:21     Самый редко встречающийся элемент в массиве #24
koto_fey, если вопросов нет, значит вам все понятно.

Добавлено через 55 секунд
Цитата Сообщение от Tulosba Посмотреть сообщение
Плохо только, что:
- unsigned;
- опущен int;
Почему плохо то? Это ведь равносильные описание типа. (unsigned int, unsigned)
koto_fey
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 90
12.01.2014, 09:18  [ТС]     Самый редко встречающийся элемент в массиве #25
Да я уж спать лег в самый разгар темыу нас то 3 ночи было.
Вопросы чуть позже буду задовать и буду рад если на них ответят.

Добавлено через 47 секунд
вопросы позже буду задавать и если на них ответят буду очень рад.
outoftime
12.01.2014, 09:57
  #26

Не по теме:

koto_fey, а ты вставляй ссылки на имена, к кому обращаешься, тогда этому человеку придет сообщение что его упомянули "..не злим тихим словом.." Т.Г. Шевченко (:

koto_fey
4 / 4 / 1
Регистрация: 11.01.2013
Сообщений: 90
12.01.2014, 11:16  [ТС]     Самый редко встречающийся элемент в массиве #27
outoftime,
q=s[i];
Freq[q]++;
можешь пояснить вот это или как так получается что мы индексируем символом. Я че то в нашей нет помойке ни чего не нашел.

Добавлено через 32 секунды
Это из второго поста

Добавлено через 3 минуты
Аааа! Кажись допер.
Получается что мы передаем массиву строку и потом как индекс ее прибавляем посимвольно, тем самым ее сканируем. Ну или вроде того.
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
12.01.2014, 12:58     Самый редко встречающийся элемент в массиве #28
Цитата Сообщение от xoror Посмотреть сообщение
В цикле идет только обнуление всех элементов массива. 256 итераций!
- это копейки.

Добавлено через 1 минуту
Цитата Сообщение от Tulosba Посмотреть сообщение
Благодаря строке 10 она у Вас как минимум квадратичная.
- с какого перепуга? Там один цикл до n...
xoror
 Аватар для xoror
29 / 31 / 2
Регистрация: 15.12.2013
Сообщений: 147
12.01.2014, 13:06     Самый редко встречающийся элемент в массиве #29
Цитата Сообщение от Catstail Посмотреть сообщение
с какого перепуга? Там один цикл
И на каждой итерации вызывается функция strlen() для вычисления длины этой строки

Цитата Сообщение от Catstail Посмотреть сообщение
C++
1
2
3
4
5
for (i=0; i<strlen(s); i++) 
{ 
   q=s[i]; 
   Freq[q]++; 
}
Сама функция strlen() примерно так выглядит
C++
1
2
3
4
5
6
7
8
9
int strlen(const char *s)
{
   int i = 0;
   
   while (s[i])
      ++i;
 
   return i;
}
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
12.01.2014, 13:13     Самый редко встречающийся элемент в массиве #30
Цитата Сообщение от xoror Посмотреть сообщение
И на каждой итерации вызывается функция strlen() для вычисления длины этой строки
- не думаю... Компилятор не так глуп.
Tulosba
:)
Эксперт C++
4377 / 3220 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
12.01.2014, 13:15     Самый редко встречающийся элемент в массиве #31
Цитата Сообщение от Catstail Посмотреть сообщение
с какого перепуга? Там один цикл до n...
см. сообщение #15 Самый редко встречающийся элемент в массиве
xoror
 Аватар для xoror
29 / 31 / 2
Регистрация: 15.12.2013
Сообщений: 147
12.01.2014, 13:30     Самый редко встречающийся элемент в массиве #32
Catstail наверно уже пожалел о том, что помог с решением задачи Вон какую критику получил
А с другой стороны это правильно. Ведь на ошибках учатся.
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
12.01.2014, 13:51     Самый редко встречающийся элемент в массиве #33
Цитата Сообщение от Catstail Посмотреть сообщение
- не думаю... Компилятор не так глуп.
Если бы вместо char* s было бы const char* s, то компилятор скорее всего соптимизировал, а так - нет
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
12.01.2014, 14:39     Самый редко встречающийся элемент в массиве #34
Цитата Сообщение от xoror Посмотреть сообщение
Вон какую критику получил
- да не критика это вовсе... Мелкая придирка. Во-первых, оптимизирующий компилятор в состоянии распознать, что в цикле строка не меняется, так что нет необходимости перевычислять эту длину на каждом витке. А во-вторых, код легко чуть подправить, и база для "критики" исчезнет:

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
void PrintRare(char *s)
{
    unsigned int i,min,l,Freq[256];
    char q;
 
    l=strlen(s);
 
    /* в Freq[i] будет частота символа с кодом i */ 
 
    for (i=0; i<256; i++) Freq[i]=0; /* чистим */
 
    for (i=0; i<l; i++)
    {
        q=s[i];       /* код очередного символа */
        Freq[q]++; /* увеличиваем соотв. элемент Freq */
    }
 
    /* ищем минимум частот (отличных от нуля!) */
 
    min=l;
 
    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;
        }
}
вот и все... Комментарии - по просьбе TC.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,398
12.01.2014, 15:37     Самый редко встречающийся элемент в массиве #35
Цитата Сообщение от Catstail Посмотреть сообщение
Во-первых, оптимизирующий компилятор в состоянии распознать, что в цикле строка не меняется, так что нет необходимости перевычислять эту длину на каждом витке.
вы попробуйте тест запустить, у меня вот совершенно разный результат выдает. Да даже если разница заметна лишь в дебаге, юнит тесты никто не отменял.
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
12.01.2014, 21:13     Самый редко встречающийся элемент в массиве #36
Цитата Сообщение от MrGluck Посмотреть сообщение
совершенно разный результат выдает
- разный с чем?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4919 / 2662 / 243
Регистрация: 29.11.2010
Сообщений: 7,398
12.01.2014, 21:17     Самый редко встречающийся элемент в массиве #37
Цитата Сообщение от Catstail Посмотреть сообщение
- разный с чем?
разный при использовании
C++
1
2
l=strlen(s);
for (i=0; i<l; i++)
и
C++
1
for (i=0; i < strlen(s); i++)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2014, 21:46     Самый редко встречающийся элемент в массиве
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
 Аватар для Catstail
21423 / 10208 / 1662
Регистрация: 12.02.2012
Сообщений: 17,082
12.01.2014, 21:46     Самый редко встречающийся элемент в массиве #38
Вероятно, это зависит от реализации компилятора.
Yandex
Объявления
12.01.2014, 21:46     Самый редко встречающийся элемент в массиве
Ответ Создать тему
Опции темы

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