найти количество одинаковых целых чисел в векторе
У меня есть вектор целых чисел. Я хочу посчитать те же самые числа в векторе. Мне нужен простой алгоритм для этого. Но без использования слишком большого количества заголовков или встроенных функций, просто с помощью простого алгоритма.
Спасибо большое
пример:
std::v={1,1,1,2,2,3} 1:3----2:2----3: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;
Другие решения
Существует как минимум два подхода: наиболее распространенное решение выполняется за время 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;
}
Другое решение — создать дополнительный словарь от int до int. И вставьте числа (как ключи) из вектора в словарь. Если число существует, вам следует увеличить значение соответствующего ключа.
Заметка. Этот словарь (карта) хранит число вхождений целых чисел от вашего вектора
Недостаток метода (с вашей точки зрения) — вы должны включить заголовок карты.
Общая сложность такого алгоритма составляет O (N log N). Может быть, такой алгоритм будет быстрее, чем использование сортировки. Вы не будете использовать один дополнительный ход. И у вас есть структура, которая имеет информацию о появлении чисел