Найти количество одинаковых целых чисел в векторе

Question

У меня есть вектор целых чисел. Я хочу посчитать те же самые числа в векторе. Мне нужен простой алгоритм для этого. Но без использования слишком большого количества заголовков или встроенных функций, просто с помощью простого алгоритма. Большое спасибо пример:

std::v={1,1,1,2,2,3} 1:3----2:2----3:1

Answer 1

Сортируйте их, а затем подсчитывайте каждое изменение в следующих цифрах.

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

попробуй после сортировки:

int count = 1;
for(int i = 1; i < v.size(); i++)
{
    if(v[i-1] == v[i])
    {
        count++;
    }
    else
    {
        std::cout << v[i-1] << count << std::endl;
        count = 0;
    }
}
std::cout << v[v.size()-1] << count << std::endl;

Answer 2

Существует как минимум два подхода: наиболее распространенное решение выполняется за время O( n log n), которое требует сортировки массива, а затем итерации по нему для подсчета самого длинного прогона, как описано в @yd1.

Другой подход заключается в использовании хеш-таблицы для генерации таблицы частот. Это выполняется за время O(n) (при условии вставки и поиска хеш-таблицы O(1)), но неоптимально для небольших длин входного вектора из-за накладных расходов на настройку хеш-таблицы и необходимости перераспределения хеш-таблицы (и коллизий и т. Д.).

Вам не нужно #include <unordered_map> использовать хеш-таблицу: самостоятельная реализация - это упражнение для студентов:) Но вам придется много работать, чтобы получить хотя бы необходимый минимум необходимых функций.

Однако, если вы можете гарантировать, что диапазон значений в векторе находится в некоторых подходящих границах (например, 0 <= i < 256) тогда вы можете использовать массив в качестве карты:

vector<int> values = ...

int table[256] = {0};
for( auto i = values.begin(); i != values.end(); ++i ) {

    assert( 0 <= i && i < 256 );

    table[*i]++;
}

Затем перебрать table чтобы узнать, какие значения одинаковы:

for( size_t i = 0; i < 256; ++i ) {

    if( table[i] > 1 ) cout << i << " appeared " << table[i] << " times." << endl;
}

Answer 3

Другое решение - создать дополнительный словарь от int до int. И вставьте числа (как ключи) из вектора в словарь. Если число существует, вам следует увеличить значение соответствующего ключа.

Заметка. Этот словарь (карта) хранит число вхождений целых чисел от вашего вектора

Недостаток метода (с вашей точки зрения) - вы должны включить заголовок карты.

Общая сложность такого алгоритма составляет O( N log N). Может быть, такой алгоритм будет быстрее, чем использование сортировки. Вы не будете использовать один дополнительный ход. И у вас есть структура, которая имеет информацию о появлении чисел