Как выбрать наиболее распространенные числа из вектора или по массиву? (TOP5 toplist) C ++

Question

У меня есть вектор с целыми числами. Я хотел бы выбрать наиболее распространенные номера. Я хотел бы сделать список топ-5. Например:

std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};

наиболее распространенные числа: ТОП 1: 32, ТОП 2: 11, ТОП 3: 12, ТОП 4: 9;

после того, как я выбрал их, я хотел бы сохранить его в другом векторе: самые распространенные числа.

Answer 1

Вот еще один алгоритм, стоимость будет O (n) для любого k, плюс приличная локальность кэша.

1.Первое сохранение всех элементов в unordered_map O (N)

std::unordered_map<int, int> m;
for(const auto ele: numbers) {
  m[ele]++;   
}

2.Сбросить все элементы в векторе пар O (N)

std::vector<std::pair<int, int>> temp;  
for(const auto& ele: m) {
 temp.emplace_back(ele.first ,  ele.second);   
}

3. Теперь использовать nth_element для нахождения k-го ранга O (N)

std::nth_element( temp.begin(), temp.begin()+k ,
temp.end(), [](const auto& p1, const auto& p2) {
        // Strict weak ordering
        if (p1.second > p2.second) {
            return true;
        }  if (p1.second < p2.second) {  
            return false;
        }
        return p1.first > p2.first; // We have to print large element first
    } );

4. Отображение вывода

std::for_each( temp.begin(), temp.begin() +k - 1, [](const auto & p) {
    std::cout << p.first << " ";
});

Демо здесь

Answer 2

Вы можете создать unordered_map<int,int> mp, где вы можете хранить счетчик каждого числа, например mp[32] = 3.

Далее вам нужно найти пять верхних элементов

1. Сложность времени: O (mlogm) : Вы можете отсортировать карту в порядке убывания ( чтобы отсортировать его, вам нужно будет использовать дополнительный вектор) и взять первые 5 элементов.

2. Сложность времени: O (m) : Или вы можете выполнить итерацию 5 раз по всей карте, чтобы получить верхние элементы файла. Каждый раз, когда вы выполняете итерацию, найдите число с наибольшей частотой, которого пока нет в нашем векторе topFive.

m: количество записей на карте.

Answer 3

вы можете сделать это: создать набор, чтобы избавиться от дубликатов, а затем найти частоту каждого элемента набора в векторе, с этим результатом создать пару (что-то вроде int, int) pu sh the создайте пару в векторе и, наконец, отсортируйте ее, используя собственный предикат:
теперь для верхнего x вы можете сделать a для l oop или просто изменить размер вектора, если вы уверены, каковы последствия этого.

std::vector<int> numbers{32, 32, 32, 12, 12, 11, 11, 11, 9};
std::set<int> mySet(numbers.begin(), numbers.end());
std::vector<std::pair<int, int>> result{};

for(const auto& x : mySet)
{
    result.push_back(std::make_pair(x , std::count(numbers.begin(), numbers.end(), x)));
}
std::sort(result.begin(), result.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b){return (b.second < a.second);});
//result.resize(3);
std::cout << "Top: " << std::endl;
for(const auto& x : result)
{
   std::cout << x.first << ':' << x.second << std::endl;
}

результат будет:

Вверх: 11: 3 32: 3 12: 2 9: 1

Answer 4

Я сделал этот пример и разместил комментарии в строке. Требуется минимум C ++ 11.

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

int main(void) {
  std::map<int, int> ans;
  std::vector<int> numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};
  std::vector<std::pair<int, int>> sorted;
  std::vector<int> common;
  // Step 1 Accumulate into a map, counting occurrences
  for (auto number : numbers) {
    ans[number]++;
  }
  // Step 2 Make a linear list, putting the count first then the value
  for (auto& ent : ans) {
    sorted.emplace_back(ent.second, ent.first);
  }
  // Step 3 sort it, by count ascending
  std::sort(std::begin(sorted), std::end(sorted));

  // Step 4 Get commonest 5 (or fewer)
  for (int i = 1; i<= 5; ++i) {
    int index = sorted.size() - i;
    if (index >= 0) {
      common.push_back(sorted[index].second);
    }
  }

  // Step 5 print out
  for (auto i : common) {
    std::cout << i << std::endl;
  }
  return 0;
}

Answer 5

Есть много способов, как этого добиться. Один из которых может быть.

std::vector numbers = {32, 32, 32, 12, 12, 11, 11, 11, 9};
int maxNumber = *std::max_element(numbers.begin(), numbers.end())
std::vector<int> occurrences(maxNumber + 1, 0);
for(auto& value : numbers)
{
   occurrences[value]++;
}

Тогда вам просто нужно отсортировать массив, отслеживая при этом индексы. Это топи c другого вопроса С ++ сортировка и отслеживание индексов .