0

我想解决以下问题：给定一个包含 n 个元素的向量，找出插入排序算法需要排序的交换次数。

例如：
n = 5
2 1 3 1 2
答案：4

说明（插入排序算法的逐步说明）：
initialy: 2 1 3 1 2
1 2 3 1 2 ; 1交换 1( 1 向左走)
1 2 3 1 2 ; 0次交换
1 1 2 3 2 ; 2 次交换（1 左 2 位）
1 1 2 2 3；1 个交换（2 去 1 个位置）

我的解决方案

我将每个项目的位置保留在初始数组中，以便稍后根据值和位置从集合中删除。（第一个 for 循环）
然后我计算小于当前数字的元素数量，将它们添加到计数器并从集合中移除该元素。（第二个for循环）

如您所见，问题在于具有线性复杂性的 std::distance集具有双向迭代器。如何在不必实现自己的树的情况下获得 O(1) 复杂性？

int count_operations(vector<int> &v)
{
    set<pair<int, int>> s;
    // O(N * logN)
    for(int i = 0; i < (int) v.size(); ++i)
    {
        s.insert(make_pair(v[i], i));
    }
    int cnt = 0;
    // desired: O(N * log N) ; current O(N^2)
    for(int i = 0; i < (int) v.size(); ++i)
    {
        auto item = make_pair(v[i], i);
        auto it = s.find(item);
        int dist = distance(s.begin(), it);//O(N); I want O(1)
        s.erase(it);
        cnt += dist;
    }
    return cnt;
}
4

1 回答 1

1

问题是获取集合中每个元素的排名，这可以使用顺序统计树（使用 gnu libc++ 中的 pbds 库）来完成，如下所示。

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>
#include <utility>
using namespace std;
using namespace __gnu_pbds;

typedef tree<
    pair<int, int>, /* key type */
    null_mapped_type, /* value type */
    less< pair<int, int> >, /* comparison */
    rb_tree_tag, /* for having an rb tree */
    tree_order_statistics_node_update> order_set;

int count_ops(std::vector<int> &v)
{
    order_set s;
    int cnt = 0;
    /* O(N*log(N)) */
    for(int i = 0; i < v.size(); i++)
        s.insert(pair<int, int>(v[i], i));
    for(int i = 0; i < v.size(); i++)
    {
        /* finding rank is O(log(N)), so overall complexity is O(N*log(N)) */
        cnt += s.order_of_key(pair<int, int>(v[i], i));
        s.erase(pair<int, int>(v[i], i));
    }
    return cnt;
}
于 2013-08-10T14:50:45.153 回答