Алгоритм вычисления режима
Я пытаюсь разработать алгоритм в виде функции, которая принимает два параметра, массив и размер массива. Я хочу, чтобы он возвращал режим массива и, если есть несколько режимов, возвращает их среднее значение. Моя стратегия состояла в том, чтобы взять массив и сначала отсортировать его. Затем посчитайте все вхождения числа. пока происходит это число, добавьте его к счетчику и сохраните его в массиве m. Таким образом, m содержит все значения, а другой массив q содержит последнее значение, которое мы сравнивали.
Например: мой список {1, 1, 1, 1, 2, 2, 2}
тогда я бы m[0] = 4 q[0] = 1
and then m[1] = 3 and q[1] = 2.
так что режим q[0] = 1;
к сожалению, я до сих пор не добился успеха. надеясь, что кто-то может помочь.
float mode(int x[],int n)
{
//Copy array and sort it
int y[n], temp, k = 0, counter = 0, m[n], q[n];
for(int i = 0; i < n; i++)
y[i] = x[i];
for(int pass = 0; pass < n - 1; pass++)
for(int pos = 0; pos < n; pos++)
if(y[pass] > y[pos]) {
temp = y[pass];
y[pass] = y[pos];
y[pos] = temp;
}
for(int i = 0; i < n;){
for(int j = 0; j < n; j++){
while(y[i] == y[j]) {
counter++;
i++;
}
}
m[k] = counter;
q[k] = y[i];
i--; //i should be 1 less since it is referring to an array subscript
k++;
counter = 0;
}
}
Решение
Хотя у вас уже есть хорошие ответы, я решил опубликовать другой. Я не уверен, что это действительно добавляет много нового, но я совсем не уверен, что это не так. Если ничего другого, я уверен, что он использует больше стандартных заголовков, чем любой другой ответ. 🙂
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <iostream>
#include <utility>
#include <functional>
#include <numeric>
int main() {
std::vector<int> inputs{ 1, 1, 1, 1, 2, 2, 2 };
std::unordered_map<int, size_t> counts;
for (int i : inputs)
++counts[i];
std::multimap<size_t, int, std::greater<size_t> > inv;
for (auto p : counts)
inv.insert(std::make_pair(p.second, p.first));
auto e = inv.upper_bound(inv.begin()->first);
double sum = std::accumulate(inv.begin(),
e,
0.0,
[](double a, std::pair<size_t, int> const &b) {return a + b.second; });
std::cout << sum / std::distance(inv.begin(), e);
}
По сравнению с ответом @ Dietmar, это должно быть быстрее, если у вас много повторений в цифрах, но, вероятно, он будет быстрее, если цифры в основном уникальный.
Другие решения
Основываясь на комментарии, кажется, вам нужно найти значения, которые встречаются чаще всего, и, если несколько значений встречаются одинаковое количество раз, вам нужно получить среднее значение из них. Кажется, это легко сделать std::sort() следуя поиску, где значения меняются и сохраняя несколько счетчиков:
template <int Size>
double mode(int const (&x)[Size]) {
std::vector<int> tmp(x, x + Size);
std::sort(tmp.begin(), tmp.end());
int size(0); // size of the largest set so far
int count(0); // number of largest sets
double sum(0); // sum of largest sets
for (auto it(tmp.begin()); it != tmp.end(); ) {
auto end(std::upper_bound(it, tmp.end(), *it));
if (size == std::distance(it, end)) {
sum += *it;
++count;
}
else if (size < std::distance(it, end)) {
size = std::distance(it, end);
sum = *it;
count = 1;
}
it = end;
}
return sum / count;
}
Если вы просто хотите посчитать количество случаев, я предлагаю вам использовать std::map или же std::unordered_map,
Если вы отображаете счетчик для каждого отдельного значения, то подсчитать вхождения, используя std::map поскольку каждый ключ может быть вставлен только один раз. Чтобы перечислить различные числа в вашем списке, просто выполните итерации по карте.
Вот пример того, как вы могли бы сделать это:
#include <cstddef>
#include <map>
#include <algorithm>
#include <iostream>
std::map<int, int> getOccurences(const int arr[], const std::size_t len) {
std::map<int, int> m;
for (std::size_t i = 0; i != len; ++i) {
m[arr[i]]++;
}
return m;
}
int main() {
int list[7]{1, 1, 1, 1, 2, 2, 2};
auto occurences = getOccurences(list, 7);
for (auto e : occurences) {
std::cout << "Number " << e.first << " occurs ";
std::cout << e.second << " times" << std::endl;
}
auto average = std::accumulate(std::begin(list), std::end(list), 0.0) / 7;
std::cout << "Average is " << average << std::endl;
}
Выход:
Number 1 occurs 4 times
Number 2 occurs 3 times
Average is 1.42857
Вот рабочая версия вашего кода. m хранит значения в массиве, а q сохраняет их количество. В конце он проходит через все значения, чтобы получить максимальное количество, сумму режимов и количество различных режимов.
float mode(int x[],int n)
{
//Copy array and sort it
int y[n], temp, j = 0, k = 0, m[n], q[n];
for(int i = 0; i < n; i++)
y[i] = x[i];
for(int pass = 0; pass < n - 1; pass++)
for(int pos = 0; pos < n; pos++)
if(y[pass] > y[pos]) {
temp = y[pass];
y[pass] = y[pos];
y[pos] = temp;
}
for(int i = 0; i < n;){
j = i;
while (y[j] == y[i]) {
j++;
}
m[k] = y[i];
q[k] = j - i;
k++;
i = j;
}
int max = 0;
int modes_count = 0;
int modes_sum = 0;
for (int i=0; i < k; i++) {
if (q[i] > max) {
max = q[i];
modes_count = 1;
modes_sum = m[i];
} else if (q[i] == max) {
modes_count += 1;
modes_sum += m[i];
}
}
return modes_sum / modes_count;
}