Нахождение частоты чисел в заданной группе чисел

Question

Предположим, у нас есть вектор/массив в C++, и мы хотим посчитать, какой из этих N элементов имеет максимальное количество повторяющихся вхождений, и вывести наибольшее количество.Какой алгоритм лучше всего подходит для этой работы.

пример:

int a = { 2, 456, 34, 3456, 2, 435, 2, 456, 2}

результат равен 4, потому что 2 встречается 4 раза.Это максимальное количество раз, которое встречается 2.

Answer 1

Отсортируйте массив, а затем выполните быстрый проход, чтобы подсчитать каждое число.Алгоритм имеет сложность O(N*logN).

Альтернативно создайте хеш-таблицу, используя число в качестве ключа.Сохраните в хеш-таблице счетчик для каждого введенного вами элемента.Вы сможете посчитать все элементы за один проход;однако сложность алгоритма теперь зависит от сложности вашей функции hasing.

Answer 2

Оптимизирован для пространства:

Быстрая сортировка (например), затем перебирает элементы, отслеживая только наибольшее количество.В лучшем случае O(N log N).

Оптимизировано по скорости:

Перебирайте все элементы, отслеживая отдельные значения.Этот алгоритм всегда будет O(n).

Answer 3

Если у вас есть ОЗУ и ваши значения не слишком велики, используйте сортировка по подсчету.

Answer 4

Возможная реализация C++, использующая STL, может быть следующей:

#include <iostream>
#include <algorithm>
#include <map>

// functor
struct maxoccur
{
    int _M_val;
    int _M_rep;

    maxoccur()
    : _M_val(0),
      _M_rep(0)
    {}

    void operator()(const std::pair<int,int> &e)
    {
        std::cout << "pair: " << e.first << " " << e.second << std::endl;
        if ( _M_rep < e.second ) {
            _M_val = e.first;
            _M_rep = e.second;
        }
    }
};

int
main(int argc, char *argv[])
{
    int a[] = {2,456,34,3456,2,435,2,456,2};
    std::map<int,int> m; 

    // load the map
    for(unsigned int i=0; i< sizeof(a)/sizeof(a[0]); i++) 
        m [a[i]]++;

    // find the max occurence...
    maxoccur ret = std::for_each(m.begin(), m.end(), maxoccur());
    std::cout << "value:" << ret._M_val << " max repetition:" << ret._M_rep <<  std::endl;

    return 0;
}

Answer 5

немного псевдокода:

//split string into array firts
strsplit(numbers) //PHP function name to split a string into it's components
i=0
while( i < count(array))
 {
   if(isset(list[array[i]]))
    {
      list[array[i]]['count'] = list + 1
    }
   else
    {
      list[i]['count'] = 1
      list[i]['number']
    }
   i=i+1
 }
usort(list) //usort is a php function that sorts an array by its value not its key, Im assuming that you have something in c++ that does this
print list[0]['number'] //Should contain the most used number

Answer 6

Алгоритм хеширования (build count[i] = #occurrences(i) в основном за линейное время) очень практичен, но теоретически не является строго O(n), поскольку во время процесса могут возникнуть хэш-коллизии.

Интересным частным случаем этого вопроса является алгоритм большинства, в котором вы хотите найти элемент, который присутствует как минимум в n/2 записях массива, если такой элемент существует.

Вот быстрое объяснение, и более подробное объяснение о том, как сделать это за линейное время, без каких-либо хэш-хитростей.

Answer 7

Если диапазон элементов велик по сравнению с количеством элементов, я бы, как говорили другие, просто сортировал и сканировал.Это время n*log n и никакого дополнительного места (возможно, log n дополнительно).

Проблема сортировки по подсчету заключается в том, что если диапазон значений велик, инициализация массива по подсчету может занять больше времени, чем сортировка.

Answer 8

Вот моя полная, протестированная версия, использующая std::tr1::unordered_map.

Я делаю это примерно за O(n).Сначала он перебирает n входных значений, чтобы вставить/обновить счетчики в unordered_map, то он делает partial_sort_copy что равно O(n).2*О(п) ~= О(п).

#include <unordered_map>
#include <vector>
#include <algorithm>
#include <iostream>

namespace {
// Only used in most_frequent but can't be a local class because of the member template
struct second_greater {
    // Need to compare two (slightly) different types of pairs
    template <typename PairA, typename PairB>
    bool operator() (const PairA& a, const PairB& b) const
        { return a.second > b.second; }
};
}

template <typename Iter>
std::pair<typename std::iterator_traits<Iter>::value_type, unsigned int>
most_frequent(Iter begin, Iter end)
{
    typedef typename std::iterator_traits<Iter>::value_type value_type;
    typedef std::pair<value_type, unsigned int> result_type;

    std::tr1::unordered_map<value_type, unsigned int> counts;

    for(; begin != end; ++begin)
        // This is safe because new entries in the map are defined to be initialized to 0 for
        // built-in numeric types - no need to initialize them first
        ++ counts[*begin];

    // Only need the top one at this point (could easily expand to top-n)
    std::vector<result_type> top(1);

    std::partial_sort_copy(counts.begin(), counts.end(),
                           top.begin(), top.end(), second_greater());

    return top.front();
}

int main(int argc, char* argv[])
{
    int a[] = { 2, 456, 34, 3456, 2, 435, 2, 456, 2 };

    std::pair<int, unsigned int> m = most_frequent(a, a + (sizeof(a) / sizeof(a[0])));

    std::cout << "most common = " << m.first << " (" << m.second << " instances)" << std::endl;
    assert(m.first == 2);
    assert(m.second == 4);

    return 0;
}

Answer 9

Это будет за O(n)............но дело в том, что нет.массива может принимать другой массив того же размера...........

для (я = 0; я

мар=счет[о];индекс = о;

для (я = 0; я

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

здесь a[] — это массив данных, в котором нам нужно найти максимальное появление определенного номера.в массиве.......

count[] имеет количество каждого элемента..........Примечание :мы уже знаем, что диапазон данных будет в массиве..скажем, например.данные в этом массиве варьируются от 1 до 100.......затем создайте массив счетчиков из 100 элементов для отслеживания, если это произошло, увеличьте индексированное значение на единицу........