1

假设我有一个这样的表：（表是 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++
4

2 回答 2

2

如果您的数据像示例中那样排序，那么它只是 O(n)。

使用 std::sort（或任何其他 O(nlogn) 排序）对数组进行排序。然后它只是另一个通过，它完成了:)

于 2013-01-18T07:54:04.327 回答
0

O(N log N)这是复杂性的一个工作示例。它首先对数据进行排序，然后遍历每个元素并通过查找第一个不匹配来计算出现次数，然后将当前元素的计数总和存储在结果向量中。请注意，您的初始数组中的计数也可以不同于 1。该代码无需指定特定的比较函数即可工作，因为std::array已经有一个 lexicographic operator<。

下面的代码使用了可能无法在您的编译器上运行的 C++11 功能（自动、lambda）。您也可以使用 initalizer 列表在一个语句中初始化向量，但是使用一对 int 和数组的嵌套向量，我对需要编写多少个大括号有点困惑 :-)

#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跳过了已搜索的元素。

于 2013-01-18T08:38:33.013 回答