找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 670|回复: 0
收起左侧

[讨论] Sort Numbers with Swap III

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-2-2015 10:54 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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;
        }
};








您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表