Используя двойные массивы, чтобы найти режим?
Я застрял на том, как написать функцию, которая находит режим или режимы набора целых чисел, содержащихся в массиве, используя этот массив и его длину в качестве параметров. Я нашел несколько решений в Интернете о том, как найти режим массива, но я пытаюсь решить эту проблему следующим образом:
Допустим, исходный массив содержит (0, 0, 1, 5, 5, 5, 7, 7, 7). Я хочу перебрать массив с циклом, который находит наибольшую частоту из всех величин без сохранения режима, и сохранить эти частоты в другом массиве, где в этом случае новый массив будет иметь значения (1, 2, 1, 1, 2, 3, 1, 2, 3). Найдя максимальное значение во втором массиве, я бы нашел самую высокую частоту, равную 3 в этом случае. Затем я хочу снова выполнить итерацию по исходному массиву, сравнивая наибольшую частоту со счетчиками каждого из значений в этом массиве, и там, где есть совпадение, я возвращаю это значение, которое в этом примере равно 5 и 7. давая. Учитывая критерии здесь, как бы вы написали эту функцию для поиска режима или режимов данного массива? (Можно предположить, что массив уже был предварительно отсортирован в порядке возрастания).
Редактировать: Вот мой предварительный код. Я дошел до шага, где я нахожу частоты каждого целого числа в исходном массиве и сохраняю их в другом массиве.
void findMode(int array, int size){
int count = 1;
int freq[size];
freq[0] = count;
for (int pass = 1; pass < size; pass++){
if (array[pass] == array[pass-1]){
count++;
freq[pass] = count;
}
else{
count = 1;
freq[pass] = count;
}
}
Решение
Если вы не возражаете против некоторого дополнительного хранилища (потенциально O(N) хранение) вы могли бы использовать std::map чтобы получить количество и затем линейный поиск наиболее часто встречающегося числа.
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <map>
#include <vector>
template<class InputIterator>
auto mode(InputIterator first, InputIterator last)
{
using key_type = typename std::iterator_traits<InputIterator>::value_type;
std::map<key_type, std::size_t> counts;
for (auto it = first; it != last; ++it) {
counts[*it]++;
}
return *std::max_element(counts.cbegin(), counts.cend(), [](auto const& lhs, auto const& rhs) {
return lhs.second < rhs.second;
}); // return mode + frequency
}
int main() {
auto v = std::vector<int> { 0, 0, 1, 5, 5, 5, 7, 7, 7 };
auto m = mode(v.cbegin(), v.cend());
std::cout << m.first << ": " << m.second;
}
Живой пример // печатает 5: 3
Другие решения
Других решений пока нет …