LeetCode493—翻转对

排序 树状数组 离散化 二分查找

第一次提交的代码：（树状数组+离散化+二分查找）

class Solution 
{
    public int[] tree;
    public long[] a;
    public int n,size;
    public int reversePairs(int[] nums) 
    {
        int ans=0;
        n=nums.length;
        Discentralize(nums);
        for(int i=n-1;i>=0;i--)
        {
            int id=getId(nums[i]),id2=getId((long)nums[i]*2);//小心乘法爆int！设long即可
            ans+=Query(id-1);//先查询答案再添加！否则自己就有可能和自己成逆序对了QAQ
            Add(id2);//因为查询的都是num*2,所以添加的也是num*2
        }
        return ans;
    }
    public void Add(int x)//树状数组模板
    {
        for(;x<=size;x+=x&-x) tree[x]++;
    }
    public int Query(int x)//树状数组模板
    {
        int tot=0;
        for(;x>0;x-=x&-x) tot+=tree[x];
        return tot;
    }
    public void Discentralize(int[] nums) //将数组离散化：去重+编号（分配的编号就是位置标号+1）
    {
        Set<Long> set=new HashSet<>();//利用HashSet的元素不同的特性来去重
        for (long num:nums) 
        {
            set.add(num);
            set.add(num*2);//因为树状数组要维护num*2，所以也要将其离散化，给其一个标号
        }
        size=set.size();
        a=new long[size];
        tree=new int[size+5];
        int index=0;
        for (long num:set) a[index++] = num;//for(long num:set)能实现对整个容器/数组的遍历
        Arrays.sort(a);
    }
    public int getId(long w)//二分查找确定每个数的编号
    {
        int L=0,R=size-1;
        while(L<R)
        {
            int mid=L+R>>1;
            if(a[mid]>=w) R=mid;
            else L=mid+1;
        }
        return R+1;
    }
}

第二次提交的代码：（归并排序）

class Solution 
{
    public int n,ans=0;
    public int reversePairs(int[] nums) 
    {
        n=nums.length;
        Merge(nums,0,n-1);
        return ans;
    }
    public void Merge(int[] nums,int L,int R)//实现归并排序的函数，应用分治思想
    {
        if(L==R) return;//分治终止条件
        int mid=(L+R)/2;
        Merge(nums,L,mid);Merge(nums,mid+1,R);
        int i=L,j=mid+1;
        for(;i<=mid;i++)
        {
            while(j<=R&&nums[i]>(long)nums[j]*2) j++;//不要在j++后面搞j--,不如直接在统计时-1
            ans+=(j-mid-1);   
        }  
        //统计答案过程不能放Sort里，因为有些有序数组也存在翻转对
        if(nums[mid]>nums[mid+1]) Sort(nums,L,mid,R); //如果两子数组合并后无序，则进行合并排序
    }
    public void Sort(int[] nums,int L,int mid,int R)//将两个有序数组合并成一个有序数组
    {
        int[] t=new int[R-L+1];//开n大小的数组会超级慢QAQ
        int i=L,j=mid+1;
        for(int k=L;k<=R;k++)
            if(i>mid) t[k-L]=nums[j++];
            else if(j>R) t[k-L]=nums[i++];
            else if(nums[i]<=nums[j]) t[k-L]=nums[i++];
            else t[k-L]=nums[j++];
        for(int k=L;k<=R;k++) nums[k]=t[k-L];//将旧数组替换为已排好序的数组
    }
}