|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
本帖最后由 uuuouou 于 10-2-2015 10:57 PM 编辑
从题目上看,只能交换相邻的两个,这是bubble sort的规则,很容易想到直接bubble sort一次统计swap的次数即可,这样做是O(N^2)的,由于题目中N最大是10万,就会超时了。我们回过头来看bubble sort,它什么时候会进行swap呢,就是发现a【i】 > a[i+1]的时候,swap两者之后如果发现还有a[i+1] > a[i+2],则继续swap。我们可以发现,对于一个数a【i】,a[i+1]~a[n-1]有多少个比它小的,即有多少个逆序对,我们就要swap多少次a【i】。更重要的是,将a【i】 swap到位之后,a[i-1]的逆序对个数并不受影响,即该对a[i-1] swap几次还是要继续swap几次。
从而问题转化为对每个a【i】统计a[i+1]~a[n-1]有多少个比自己小的数,利用树状数组便可以在O(NlogN)的时间复杂度下完成:class Solution {
private:
static const int MAX_N = 100000;
typedef long long LL;
LL c[MAX_N + 5];
LL sum(int x){
LL s = 0;
for(; x; x -= x&-x) s += c[x];
return s;
}
void add(int x, int n){
for(; x <= n; x += x&-x) ++c[x];
}
public:
long long sortWithSwap(vector<int> &a) {
int n = a.size();
if(n < 2) return 0;
memset(c, 0, (n+1)*sizeof(LL));
LL tot = 0;
for(int i = n-1; i > -1; --i){
tot += sum(a【i】);
add(a【i】 + 1, n);
}
return tot;
}
};
|
|