Как посчитать количество повторяющихся элементов в массиве? Пример (1,2,3,4,5,6,7,8,9,1,2,4,6,8,2,1)
1-3 раза
2-2 раза
3-1 раз
4-2 раза и т.д.
Только чтобы не повторялись числа массива на выходе.

если диапазон чисел невелик, например от 0 до 10, то быстрее всего будет работать массив счётчиков, i-й эелмент которого содержит число повторений числа i:



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



Это сообщение отредактировал(а) baldina - 11.5.2010, 19:14

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

что это?

что-то вроде vector<bool> или bitset

Это сообщение отредактировал(а) azesmcar - 11.5.2010, 20:34

azesmcar, а как это юзать в этой задаче?

как-то так

ну и уже результат записывать куда угодно, map наверно удобнее всего.

Это сообщение отредактировал(а) azesmcar - 11.5.2010, 21:06

azesmcar, это сумма повторов элементов, ТСу надо не это

алсо ваш код мне чем-то напомнил примеры по C#, там где if(cond)return true; else return false;

во первых

во вторых это не сложно его переделать. Я показал метод нахождения повторов, остальное можно додумать.
если использовать для поиска повторов к примеру map - для каждого элемента будет произведен поиск, что замедлит программу, в случае с массивом (т.е. использования значения как индекс, см. пример 1 baldina) поиск будет константным, но и занимать будет немало памяти, это как бы альтернатива. А хранить повторы и их количества можно в map-е, повторов будет меньше чем элементов массива.


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

Это сообщение отредактировал(а) azesmcar - 11.5.2010, 22:32

azesmcar, во первых читайте текст 1го поста полностью, ТС написал что на входе, а что на выходе.

Во-вторых, как я понял, у вас все повторы хранятся в одной переменной - count,
как туда прикрутить map, чтобы получить для каждого значения свой счетчик?

Я и не решал задачу автора, я показывал как найти повторения. Это пример поиска ПОВТОРЕНИЙ, прикрутиь сюда map очень просто, хранить ИМЕННО ПОВТОРЕНИЯ и их количества в map, их можно хранить в чем угодно, хоть в файле, сложность задачи - найти повторения и задача решена, а как организовать хранения нужных ДЛЯ ВЫВОДА данных - это другой вопрос. Сделаем проще, напишите свой вариант решения задачи автора.

Это сообщение отредактировал(а) azesmcar - 12.5.2010, 08:34

azesmcar, на спичках экономите, а исходная задача ТС так Вами и не решена   (надо найти не вообще повторения, а повторения каждого элемента множества, из постановки это ясно).



Согласен с Abyx, это масло масляное. Эквивалент

во первых я не предлагал экономить и не говорил что предложенный вами вариант ошибочен, я предложил еще один способ нахождения повторений, во вторых, это не спички а память, если в массиве не 10 элементов а несколько миллиардов - экономия получается достаточно серьезная, вместо 1-байта используется 1 бит а поиск остается константным, экономия в 8 раз не шутки. Вам никогда не приходилось писать задачи под слабые процессоры или машины с малым количеством памяти?


я и не собирался, это не центр помощи, я не решал исходную задачу а предложил еще один вариант решения, или вы считаете что так задачу решить невозможно?


это не эквивалент, эквивалент написал Abyx, тут в любом случае нужна проверка повторился ли элемент, если проверка есть - тогда какой смысл присваивать еще раз? есть ли смысл говорить о том, что vector<bool> работает через proxy класс, которые совершает битовую операцию при присваивании? в чем смысл? выйграть пару строку кода, сделав код менее читабельным?

теперь о решении
для вывода повторяющихся значений в том виде, в котором вы предоставили решение ТС надо пройтись по всем элементам массива/map-а, и проверять кажый на предмет повторения, это я так полагаю не вариант, вам надо хранить повторения раздельно, т.е. в отдельном map-е, получается используется map/vector для нахождения повторов и повторы заносяться в отдельный map, в чем же разница? это все я говорю с учетом того, что в масиве пара миллиардов значений. Повторений среди них наверняка на порядок меньше.

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

если bits[data[i]] в любом случае должен быть true, то зачем чтото проверять?
так и пишите, bits[data[i]] = true;

(и это существенно эффективнее на уровне асма)

затем, чтобы подсчитать сколько раз повторялось то или иное значение.

проведем небольшой эксперимент
через vector<bool>

результат


через set/map

результат

замена vector<bool> к примеру на vector<char> на скорость практически не влияет, зато на использование памяти влияет немало
9999999 байтов = 9.53Mb
9999999 битов = 1.19Mb
разница есть? экономия на спичках? а если в вашем распоряжении 64Mb оперативной памяти?

Это сообщение отредактировал(а) azesmcar - 12.5.2010, 20:12