VPF::Определение повторяющихся элементов в массиве

Firex

Дата 30.10.2010, 18:48 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Создаётся динамический массив из 10 значений, в него рандомно записываются числа от -10 до 10. Как наиболее рационально можно определить число, которое встречается наибольшее количество раз(и сколько раз конкретно)?
Идея такая, но может быть кто-то предложит рациональнее:
1. Создаём дополнительно структурированный массив вида

Код


struct temp
{
int var
int count
} mass[5]

В var будем писать повторившееся число, а count увеличивать на +1. Далее сортируем mass по переменной count и выводим максимальный элемент. Но тут возникает проблема... если повторившихся элементов несколько и переменная count у них одинаковая... Это лишние операции...

Annihilator

Дата 30.10.2010, 20:05 (ссылка)

(нет голосов)

Загрузка ...

bytegrinder

Профиль
Группа: Участник
Сообщений: 493
Регистрация: 21.11.2006
Где: Омск

Репутация: 1
Всего: 3

Первое, что пришло на ум - 2 счетчика завести.
Допустим ты отсортировал массив и получилось что-то типа
1 1 1 2 2 2 2 3 3 3 5 5 7 8 8 9 9 9 9 9 0
первый счетчик начала считать элементы - насчитал 3 по 1
элемент изменился - запускаем второй счетчик по двойкам. Если счетчик по двойкам больше, чем по единицам, присваиваем первому счетчику значение второго счетчика, а второй счетчик используем далее, т.е. для троек. Потом опять сравниваем с первым счетчиком и т.д.

Это сообщение отредактировал(а) Annihilator - 30.10.2010, 20:07

--------------------

Если вы не можете сделать хоpошyю пpогpаммy, сделайте, чтобы она по кpайней меpе выглядела хоpошо

Firex

Дата 30.10.2010, 20:18 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Спасибо за идею,если ничего больше не придумаю/не подскажут, то буду так делать.Но вот чувствую, что должно это как-то решаться совсем просто...
З.ы. Хотя этот вариант только для частного примера... хотелось бы масштабный вариант, не только для -10..10.
З.ы.ы. да и рациональности тут не много, имхо )

Это сообщение отредактировал(а) Firex - 30.10.2010, 20:21

Леопольд

Дата 30.10.2010, 21:37 (ссылка)

(голосов:1)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Firex, отсортировать и один раз проbежаться по массиву.

--------------------

вопросов больше чем ответов

azesmcar

Дата 31.10.2010, 08:25 (ссылка)

(голосов:1)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

Цитата(Firex @ 30.10.2010, 18:48

)

есть множество решений, конкретно для этого случае можно хранить дополнительный массив

Код


int r[21] = {0};

потом пройтись по всем элементам и сделать инкремент по индексу равному значению этого элемента +10

Код


for (int i = 0; i < size; ++i)
{
   int element = arr[i];
   ++r[element + 10];
}

в итоге получаешь массив r, в котором по индексу записаны количества повторений каждого элемента массива.
если элементов намного больше то можно использовать std::bitset (правда в этом случае будет невозможно отследить количество повторений) или std::map.

Это сообщение отредактировал(а) azesmcar - 31.10.2010, 09:42

Леопольд

Дата 31.10.2010, 17:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(azesmcar @ 31.10.2010, 08:25

)

потом пройтись по всем элементам и сделать инкремент по индексу равному значению этого элемента +10

Или использовать std::map, значение элемента - ключ.

Но вариант с сортировкой bыстрее.

Это сообщение отредактировал(а) Леопольд - 31.10.2010, 17:40

--------------------

вопросов больше чем ответов

Firex

Дата 31.10.2010, 17:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Прошу прощения тех, кто отписался, но я решил всё же пойти по своему алгоритму... Вот только проблемка одна появилась... как на вывод подать только 1 из повторяющихся значений ? А если переменная count одинакова у нескольких переменных, как быть ? Думаю стоит тогда вывести несколько разных переменных по одному разу, у которых переменная count одинакова. Собственно вопрос, что мне делать дальше? Вот код:

Код



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

struct buff // структура для записи переменной и количества совпадений
{
    int tempVar;
    int tempCount;
};
int main(int argc, char *argv[])
{
    setlocale (LC_CTYPE,"");
    srand((int)time(NULL));
    int *mass,i=10,j,t,z;
    char flag;
    struct buff vmass[i];
    mass=calloc(i,sizeof(int)); // динамический массив
    for(j=0;j<i;j++) // заполняем рандомными числами от -10 до 10
    {
        mass[j]=rand()%20-10;
        vmass[j].tempVar=mass[j]; // заносим массив в структурированный массив
        vmass[j].tempCount=0; // для каждой переменной пока количество совпадений 0
        printf("Элемент массива %d случайное число %d\n",j,mass[j]);
    };
    printf("\n");
    for(j=0;j<i;j++)
    {
        flag='f'; // совпадений нет
        t=0;
        for(z=0;z<i;z++)
        {
            if(mass[j]==mass[z]) // если есть совпадение
            {
                flag='t'; // есть совпадение
                t++; // количество совпадений
            };
        };
        if('t'==flag)
        {
            vmass[j].tempCount=vmass[j].tempCount+t; // записываем в структурированный массив количество совпадений
        };
        printf("vmass[%d].tempCount=%d vmass.tempvar=%d\n",j,vmass[j].tempCount,vmass[j].tempVar);
    };
    printf("\n");
    for(j=0;j<i;j++) // сортируем структурированный массив по переменноый Count
    {
        for(z=0;z<i-1;z++)
        {
            if(vmass[z].tempCount<vmass[z+1].tempCount)
            {
                int buff=vmass[z].tempCount;
                vmass[z].tempCount=vmass[z+1].tempCount;
                vmass[z+1].tempCount=buff;
                buff=vmass[z].tempVar;
                vmass[z].tempVar=vmass[z+1].tempVar;
                vmass[z+1].tempVar=buff;
            };
        };
    };
    for(j=0;j<i;j++)
    {
        printf("vmass[%d].tempVar=%d Count=%d\n",j,vmass[j].tempVar,vmass[j].tempCount);
//        if((vmass[j].tempCount==vmass[vmass[j].tempCount-1].tempCount)&&(vmass[j].tempVar==vmass[vmass[j].tempCount-1].tempVar)&&(vmass[j].tempCount<3))

    };
    return 0;
}

Это сообщение отредактировал(а) Firex - 31.10.2010, 17:46

azesmcar

Дата 31.10.2010, 17:52 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

Цитата(Леопольд @ 31.10.2010, 17:40

)

Или использовать std::map, значение элемента - ключ.

я уже писал об этом.

Цитата(Леопольд @ 31.10.2010, 17:40

)

Но вариант с сортировкой bыстрее.

сортировка - O(n log(n))+дальше понадобиться линейный перебор массива для поиска повторений, std::map - просто O(n log(n)), это n вставок, сложность каждой вставки O(log(n)). А в случае с вектором/bitset-ом сложность линейная O(n).

Это сообщение отредактировал(а) azesmcar - 31.10.2010, 17:56

Леопольд

Дата 31.10.2010, 18:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Код

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

int main()
{
    vector<int> data(100000);

    srand(unsigned (time(NULL)));
    generate(data.begin(), data.end(), rand);

    sort(data.begin(), data.end());

    vector<int>::const_iterator it = data.begin();
    vector<int>::const_iterator end = data.end();

    std::size_t max = 0;
    int num  = *it++;
    std::size_t count = 1;
    int result = num;

    for(;it != end; ++it)
    {
        if(*it != num)
        {
            if(max < count)
            {
                max = count;
                result = num;
            }
            num = *it;
            count = 0;
        }
        ++count;
    }

    cout<<"result = "<<result<<"\nmax = "<<max<<std::endl;

    return 0;
}

Цитата(azesmcar @ 31.10.2010, 17:52

)

я уже писал об этом.

Видимо, невнимательно читаю... smile

Это сообщение отредактировал(а) Леопольд - 31.10.2010, 18:17

--------------------

вопросов больше чем ответов

Firex

Дата 31.10.2010, 19:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Подскажите пожалуйста по моему алгоритму smile

azesmcar

Дата 31.10.2010, 19:52 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

Firex

Завтра с утра напишу если никто не опередит, сегодня как-то лень smile

Это сообщение отредактировал(а) azesmcar - 31.10.2010, 19:54

Леопольд

Дата 31.10.2010, 20:11 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(Firex @ 31.10.2010, 19:37

)

Подскажите пожалуйста по моему алгоритму

Сложно его читать...

--------------------

вопросов больше чем ответов

xvr

Дата 1.11.2010, 11:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(Firex @ 31.10.2010, 19:37)

Подскажите пожалуйста по моему алгоритму smile

Подсказываю - забыть как страшный сон. Из всех, предложенных в этом топике алгоритмов - ваш самый неэффективный (и самый прямолинейный). Единственное преимущество 'самый простой' полностью разбивается стилем реализации, типа 'черт ногу сломит'

azesmcar

Дата 1.11.2010, 12:04 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 52
Всего: 211

Цитата(xvr @ 1.11.2010, 11:53

)

'черт ногу сломит'

да уж, беглый осмотр кода сразу же отбил всякое желание лезть в эти дебри.

Firex

Дата 1.11.2010, 17:21 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Ладно, пусть плохой у меня код... тогда только подскажите дальнейшие действия, если на данной стадии я имею: структурированный массив упорядоченный по переменной vmass.tempCount(число повторений переменной), а в vmass.tempVar лежит сама переменная. Буду премного благодарен.

xvr

Дата 1.11.2010, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 35
Всего: 223

Цитата(Firex @ 1.11.2010, 17:21

)

огда только подскажите дальнейшие действия, если на данной стадии я имею: структурированный массив упорядоченный по переменной vmass.tempCount(число повторений переменной), а в vmass.tempVar лежит сама переменная.

Вывести tempVar из начала (или конца - смотря как у вас они упорядоченны)

Цитата(Firex @ 30.10.2010, 18:48

)

о тут возникает проблема... если повторившихся элементов несколько и переменная count у них одинаковая...

Не имеет значения - вам же нужен 1 максимальный? Вот один и берите.

Firex

Дата 1.11.2010, 20:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Решил следующим образом задачу, вдруг кому сгодиться) Программа ищет в массиве число, которое повторяется наибольшее количество раз, если таких чисел несколько, которые имеют равное количество повторений, то выводит их все.

Код



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <locale.h>

struct buff // структура для записи переменной и количества совпадений
{
    int tempVar;
    int tempCount;
};
int main(int argc, char *argv[])
{
    setlocale (LC_CTYPE,"");
    srand((int)time(NULL));
    int *mass,i=10,j,t,z,MaxCount=0;
    char flag;
    struct buff vmass[i];
    mass=calloc(i,sizeof(int)); // динамический массив
    for(j=0;j<i;j++) // заполняем рандомными числами от -10 до 10
    {
        mass[j]=rand()%20-10;
        vmass[j].tempVar=mass[j]; // заносим массив в структурированный массив
        vmass[j].tempCount=0; // для каждой переменной пока количество совпадений 0
        printf("Элемент массива %d случайное число %d\n",j,mass[j]);
    };
    printf("\n");
    for(j=0;j<i;j++)
    {
        flag='f'; // совпадений нет
        t=0;
        for(z=0;z<i;z++)
        {
            if(mass[j]==mass[z]) // если есть совпадение
            {
                flag='t'; // есть совпадение
                t++; // количество совпадений
            };
        };
        if('t'==flag)
        {
            vmass[j].tempCount=vmass[j].tempCount+t; // записываем в структурированный массив количество совпадений
        };
        printf("vmass[%d].tempCount=%d vmass.tempvar=%d\n",j,vmass[j].tempCount,vmass[j].tempVar);
    };
    printf("\n");
    for(j=0;j<i;j++) // сортируем структурированный массив по переменной Var
    {
        for(z=0;z<i-1;z++)
        {
            if(vmass[z].tempVar<vmass[z+1].tempVar)
            {
                int buff=vmass[z].tempVar;
                vmass[z].tempVar=vmass[z+1].tempVar;
                vmass[z+1].tempVar=buff;
                buff=vmass[z].tempCount;
                vmass[z].tempCount=vmass[z+1].tempCount;
                vmass[z+1].tempCount=buff;
            };
        };
        if(MaxCount<vmass[j].tempCount)
        {
            MaxCount=vmass[j].tempCount;
        };
    };
    z=11;
    flag='t';
    if(MaxCount!=1)
    {
        for(j=0;j<i;j++)
        {
//            printf("vmass[%d].tempVar=%d Count=%d\n",j,vmass[j].tempVar,vmass[j].tempCount);
            if((vmass[j].tempVar!=z)&&(vmass[j].tempCount==MaxCount))
            {
                if('t'==flag)
                {
                    printf("Наибольшее чисило раз(%d) встречается элемент %d\n",MaxCount,vmass[j].tempVar);
                    flag='f';
                }
                else if('f'==flag)
                {
                    printf("Элемент %d имеет такое же количество повторений\n",vmass[j].tempVar);
                };
            };
            z=vmass[j].tempVar;
        
        };
    } else printf("Все элементы встречаются по только одному разу/n");
//    printf("MaxCount=%d\n",MaxCount);
    return 0;
}

Пусть код и убогий(как говорят тут старшие товарищи)... зато рабочий и без использования всякой всячины, которая на первом курсе не прокатывает.

LeD4eG

Дата 1.11.2010, 20:05 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 115
Регистрация: 29.9.2009
Где: Волгоград

Репутация: 1
Всего: 1

а нельзя ли сделать приблизительно такое (псевдокод):

Код


max_cnt=0;    //максимальное число повторений одного числа
for(i=0;i<size_mass;i++){
    cnt_var=0;      //счётчик для переменной
    for(j=i+1;j<size_mass-1;j++){
            if(a[j]-a[i]==FLT_EPSILON){
                       cnt_var++;   //увеличиваем счётчик этой переменной
                       k =i               //запоминаем индекс повторяющегося числа
              }
             if(cnt_var>max_cnt) max_cnt=cnr_var;
       }
}

ну хотя я

--------------------

Ты не успел стать для кого-то главным, кому-то очень нужным.....

Леопольд

Дата 2.11.2010, 12:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(Firex @ 1.11.2010, 20:01

)

Когда пишешь что-то, надо разбить это что-то на элементарные подзадачи, и оперировать уже ими. Т.е. Заполнил массив - одна функция, отсортировал - другая, нашёл максимальный элемент(ы) - третья, вывел результат - четвёртая. Потом в main выполнил их по очереди. У тебя же, всё в кучу намешанно, поэтому сложно читать.

--------------------

вопросов больше чем ответов

Firex

Дата 3.11.2010, 20:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 58
Регистрация: 20.10.2010

Репутация: нет
Всего: нет

Леопольд, спасибо, буду это в последующем учитывать. Как то просто не задумывался над этим.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »