[leetcode]315. Count of Smaller Numbers After Self

問題の説明
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element. Return the array [2, 1, 1, 0].
最初はプログラミングの美しさの光影切断問題の中で逆順を求めてこの問題を見つけて、ネット上にはとても巧みな解法がたくさんあって、自分で2つを実現しました.
方法一:集計を書き換える

    private static void reverse(int[] nums, int[] smaller, int[] pos, int start, int end){
        if(start>=end){
            return ;
        }
        int mid=start+(end-start)/2;
        reverse(nums, smaller, pos, start, mid);
        reverse(nums, smaller, pos, mid+1, end);
        int[] temp=new int[end-start+1];
        int i=start, j=mid+1, k=0;
        int count=0;
        while(i<=mid||j<=end){
            if(i>mid){
                temp[k++]=pos[j++];
            }else if(j>end){
                smaller[pos[i]]+=count;
                temp[k++]=pos[i++];
            }else if(nums[pos[i]]<=nums[pos[j]]){
                smaller[pos[i]]+=count;
                temp[k++]=pos[i++];
            }else{
                count++;
                temp[k++]=pos[j++];
            }

        }       
        for(i=0; ipos[start+i]=temp[i];
        }       
    }

    public static List countSmaller(int[] nums) {
        List re=new ArrayList();
        if(nums==null||nums.length==0){
            return re;
        }
        int[] smaller=new int[nums.length];
        int[] pos=new int[nums.length];
        for(int i=0; i<pos.length; i++){
            pos[i]=i;
        }
        reverse(nums, smaller, pos, 0, nums.length-1);
        for(int i=0; ilength; i++){
            re.add(smaller[i]);
        }
        return re;
    }

元の順序を保存するため,配列を直接書き換えるのではなく,対応する位置を1つのpos配列で格納する.ブログ参照http://blog.csdn.net/jmspan/article/details/51219203
方法2:ツリー配列
ツリー配列とセグメントツリーの2つのデータ構造を学習した.次に、ツリー配列で実装されるコードを示します.

    private static int[] tree;

    //  1、       
    public static List countSmaller(int[] nums) {
        int[] temp=nums.clone();
        Arrays.sort(temp);
        for(int i=0; inew int[nums.length];
        Integer[] re=new Integer[nums.length];
        for(int i=nums.length-1; i>=0; i--){
            re[i]=sumRange(nums[i]);
            add(nums[i]+1, 1);
        }
        return Arrays.asList(re);       
    }



    private static void add(int index, int val){
        while(indexindex]+=val;
            index+=lowBit(index);
        }
    }

    private static int sumRange(int index){
        int re=0;
        while(index>0){
            re+=tree[index];
            index-=lowBit(index);
        }
        return re;
    }

    private static int lowBit(int index){
        return index&(-index);
    }

ブログ参照http://www.cnblogs.com/bigchencheng/p/5151382.html
もちろん樹状配列には改良された空間があり、元の配列を二分検索により0-numsに変更する.lengthの新しい配列は,数値を変えたが相対的な大きさは変わらないので,答えには影響しない.leetcodeディスカッションエリアでは、次のような改善が行われています.

    public static List countSmaller2(int[] nums) {
        pre(nums);
        tree=new int[11000];
        Integer[] re=new Integer[nums.length];
        for(int i=nums.length-1; i>=0; i--){
            re[i]=sumRange(nums[i]);
            add(nums[i]+1, 1);
        }       
        return Arrays.asList(re);       
    }


    private static void pre(int[] nums){
        int min=Integer.MAX_VALUE;
        for(int num: nums){
            min=Math.min(min, num);
        }
        if(min<0){
            min=-min+1;
            for(int i=0; ilength; i++){
                nums[i]+=min;
            }
        }
    }

この方法は空間的に一定の制限があるが,二分で元の配列を変えることを避けるため,この問題では時間が最も短い.リファレンスアドレスhttps://discuss.leetcode.com/topic/31154/complicated-segmentree-solution-hope-to-find-a-better-one
本題では、ツリー、セグメントツリーを二叉で検索する方法で解くこともできます.詳細はブログを参照してください.http://www.cnblogs.com/yrbbest/p/5068550.html