сжимаем таблицу: одни и те же строки перекрывают друг друга и подсчитывают количество

Question

сжимаем таблицу: одни и те же строки перекрывают друг друга и подсчитывают количество

Предположим, у меня есть такая таблица: (таблица является двумерным массивом в C ++)
число это количество для каждой строки.

1 a b c
1 a b c
1 c d e
1 b c d
1 b c d

с прижиматься к:

2 a b c
1 c d e
2 b c d

Мой алгоритм O (n * n), может кто-нибудь улучшить его?

suppose t1 is original one;
initial another t2;
row_num = 1;
copy first row of t1 to t2;

foreach row in t1 (1 to n)
search each row in t2 (0 to row_num);
if equal, then add the number;
break;
if not found, then copy current t1's row to t2;
row_num++

1

accumulate algorithm arrays c++counting

Решение

Другие решения

Если ваши данные отсортированы, как в примере, то это просто O (n).

Используйте std :: sort (или любую другую O (nlogn) sort), чтобы упорядочить ваши массивы. Тогда это просто еще один проход, и все готово 🙂

2

Источник

Accepted Answer

Вот рабочий пример O(N log N) сложность. Сначала он сортирует данные, затем перебирает каждый элемент и подсчитывает число вхождений путем поиска первого несоответствия, а затем сохраняет сумму отсчетов текущего элемента в результирующем векторе. Обратите внимание, что у вас также может быть число, отличное от 1 в ваших начальных массивах. Код работает без указания конкретной функции сравнения, потому что std::array уже есть лексикографический operator<,

Приведенный ниже код использует функции C ++ 11 (auto, lambda), которые могут не работать на вашем компиляторе. Вы также можете использовать списки инициализаторов для инициализации вектора в одном выражении, но с вложенным вектором пары int и array я немного запутался в том, сколько фигурных скобок мне нужно написать 🙂

#include <algorithm>
#include <array>
#include <iostream>
#include <utility>
#include <vector>

typedef std::pair<int, std::array<char, 3> > Element;
std::vector< Element > v;
std::vector< Element > result;

int main()
{
v.push_back( Element(1, std::array<char, 3>{{'a', 'b', 'c'}}) );
v.push_back( Element(2, std::array<char, 3>{{'a', 'b', 'c'}}) );
v.push_back( Element(1, std::array<char, 3>{{'c', 'd', 'e'}}) );
v.push_back( Element(1, std::array<char, 3>{{'b', 'c', 'd'}}) );
v.push_back( Element(3, std::array<char, 3>{{'b', 'c', 'd'}}) );

// O(N log(N) ) complexity
std::sort(v.begin(), v.end(), [](Element const& e1, Element const& e2){
// compare the array part of the pair<int, array>
return e1.second < e2.second;
});

// O(N) complexity
for (auto it = v.begin(); it != v.end();) {
// find next element
auto last = std::find_if(it, v.end(), [=](Element const& elem){
return it->second != elem.second;
});

// accumulate the counts
auto count = std::accumulate(it, last, 0, [](int sub, Element const& elem) {
return sub + elem.first;
});

// store count in result
result.push_back( Element(count, it->second) );
it = last;
}

for (auto it = result.begin(); it != result.end(); ++it) {
std::cout << it->first << " ";
for (std::size_t i = 0; i < 3; ++i)
std::cout << it->second[i] << " ";
std::cout << "\n";
}
}

Выход на Ideone

НОТА: цикл по отсортированным элементам может показаться O(N^2) (линейный std::find_if вложенный в линейный for), но это O(N) из-за последнего оператора цикла it = last который пропускает уже найденные элементы.

0