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

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

Первое, что пришло на ум -  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

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

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

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

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

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

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


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

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

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


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

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


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

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


сортировка - 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:17

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

Firex

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

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

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

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

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

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