LeetCode315—计算右侧小于当前元素的个数

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

第一次提交的代码：（归并排序+索引数组）

class Solution 
{
    public int[] count,index,t;
    public int n;
    public List<Integer> countSmaller(int[] nums) 
    {
        List<Integer> ans=new ArrayList<>();
        n=nums.length;
        count=new int[n];
        index=new int[n];
        t=new int[n];
        for(int i=0;i<n;i++) index[i]=i;
        Merge(nums,0,n-1);
        for(int i=0;i<n;i++)
            ans.add(count[i]);
            //主要是因为ArrayList里修改元素不太方便，所以统计逆序对数时不用ans而新开一个count
        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);
        if(nums[index[mid]]>nums[index[mid+1]]) Sort(nums,L,mid,R);
        //如果两子数组合并后无序，则进行合并排序
    }
    public void Sort(int[] nums,int L,int mid,int R)//将两个有序数组合并成一个有序数组
    {
        for(int i=L;i<=R;i++) t[i]=index[i];//一开始写的范围是0到n-1,然后直接超时QAQ
        int i=L,j=mid+1;
        for(int k=L;k<=R;k++)
        {
            if(i>mid) index[k]=t[j++];
            else if(j>R) 
            {
                index[k]=t[i++];
                count[index[k]]+=(R-mid);//加左边的元素时，右边比其先加的元素都构成逆序对
            }
            else if(nums[t[i]]<=nums[t[j]]) 
            {
                index[k]=t[i++];
                count[index[k]]+=(j-mid-1);//加左边的元素时，右边比其先加的元素都构成逆序对
            }
            else index[k]=t[j++];
        }
    }
}

第二次提交的代码：（树状数组）

class Solution 
{
    public int[] tree=new int[20002];
    //t是树状数组，树状数组的第i位储存着值为i-10001的数的个数。树状数组维护的是前缀和
    public List<Integer> countSmaller(int[] nums) 
    {
        List<Integer> ans=new ArrayList<>();
        int n=nums.length;
        for(int i=n-1;i>=0;i--)
        {
            int t=nums[i]+10001;//将数组元素中的负数转化为正数，方便用树状数组维护
            Add(t);
            ans.add(Query(t-1));
        }
        Collections.reverse(ans);//将数组或列表反转的内置函数
        return ans;
    }
    public void Add(int x)//树状数组模板
    {
        for(;x<=20001;x+=x&-x) tree[x]++;
    }
    public int Query(int x)//树状数组模板
    {
        int tot=0;
        for(;x>0;x-=x&-x) tot+=tree[x];//树状数组的0号位不能用，否则死循环！！！
        return tot;
    }
}

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

class Solution 
{
    public int[] tree,a;
    public int n,size;
    public List<Integer> countSmaller(int[] nums) 
    {
        List<Integer> ans=new ArrayList<>();
        n=nums.length;
        Discentralize(nums);
        for(int i=n-1;i>=0;i--)
        {
            int id=getId(nums[i]);
            Add(id);
            ans.add(Query(id-1));
        }
        Collections.reverse(ans);
        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<Integer> set=new HashSet<Integer>();//利用HashSet的元素不同的特性来去重
        for (int num:nums) set.add(num);//for (int num:nums)遍历整个nums容器的方法
        size=set.size();
        a=new int[size];
        tree=new int[size+5];
        int index=0;
        for (int num:set) a[index++] = num;
        Arrays.sort(a);
    }
    public int getId(int 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;
    }
}