三种解法 315. Count of Smaller Numbers After Self

这题跟493如出一辙。
一样的思路。brute force, merge Sort, BST, segment Tree.
先上merge sort的，

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int N = nums.length;
        int[] indexes = new int[N];
        for (int i = 0; i < N; i++) {
            indexes[i] = i;
        }
        
        int[] counts = new int[N];
        int[] helper = new int[N];
        
        mergeSort(nums, counts, helper, indexes, 0, N - 1);
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            result.add(counts[i]);
        }
        return result;
    }
    private void mergeSort(int[] nums, int[] counts,int[] helper, int[] indexes, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(nums, counts, helper, indexes, start, mid);
        mergeSort(nums, counts, helper, indexes, mid + 1, end);
        for (int i = start; i <= end; i++) {
            helper[i] = indexes[i];
        }
        
        int l = start, r = mid + 1;
        int pt = start;
        while (l <= mid && r <= end) {
            if (nums[helper[l]] <= nums[helper[r]]) {
                counts[helper[l]] += (r - (mid + 1) );
                indexes[pt++] = helper[l++];
            } else {
                
                indexes[pt++] = helper[r++];
            }
        }
        while (l <= mid) {
            counts[helper[l]] += (r - (mid + 1));
            indexes[pt++] = helper[l++];
        }
        
        while (r <= end) {
            indexes[pt++] = helper[r++];
        }
        return;
    }
}

再上BST的

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> ans = new LinkedList<>();
        TreeNode root = buildTree(nums);
        for (int i = nums.length - 1; i >= 0; i--) {
            ans.addFirst(query(root, nums[i]));
            insert(root, nums[i]);
        }
        return ans;
    }
    private TreeNode buildTree(int[] nums) {
        int[] helper = Arrays.copyOfRange(nums, 0, nums.length);
        Arrays.sort(helper);
        return buildTree(helper, 0, nums.length - 1);
    }
    private TreeNode buildTree(int[] helper, int l, int r) {
        if (l > r) return null;
        if (l == r) return new TreeNode(helper[l]);
        int mid = l + (r - l) / 2;
        TreeNode root = new TreeNode(helper[mid]);
        root.left = buildTree(helper, l, mid - 1);
        root.right = buildTree(helper, mid + 1, r);
        return root;
    }
    private void insert(TreeNode root, int num) {
        if (root == null) return;
        if (root.val == num) {
            root.repeats++;
        } else if (root.val > num) {
            root.numberSmaller++;
            insert(root.left, num);
        } else {
            insert(root.right, num);
        }
    }
    private int query(TreeNode root, int num) {
        if (root == null) return 0;
        if (root.val >= num) {
            return query(root.left, num);
        } else {
            return root.repeats + query(root.right, num) + root.numberSmaller;
        }
    }
}
class TreeNode{
    int val;
    int repeats;
    int numberSmaller;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

再上segment tree的

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        int[] minMax = getMinMax(nums);
        SegmentTreeNode root = new SegmentTreeNode(minMax[0], minMax[1]);
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = nums.length - 1; i >= 0; i--) {
            //query
            ans.addFirst(query(root, nums[i]));
            //update tree;
            update(root, nums[i]);
        }
        return ans;
    }
    private int query(SegmentTreeNode root, int num) {
        if (root == null || root.start >= num) return 0;
        if (num > root.end) return root.count;
        return query(root.left, num) + query(root.right, num);
    }
    private void update(SegmentTreeNode root, int num) {
        
        if (num < root.start || num > root.end) return;
        root.count++;
        if (root.start == root.end) return;
        int mid = root.start + (root.end - root.start) / 2;
        if (num <= mid) {
            if (root.left == null) { 
                root.left = new SegmentTreeNode(root.start, mid);
            }
            update(root.left, num);
        } else {
            if (root.right == null) {
                root.right = new SegmentTreeNode(mid + 1, root.end);
            }
            update(root.right, num);
        }
    }
    
    private int[] getMinMax(int[] nums) {
        int min = nums[0], max = nums[0];
        for (int n : nums) {
            min = min > n ? n : min;
            max = max < n ? n : max;
        }
        return new int[]{min, max};
    }
}
class SegmentTreeNode {
    int start;
    int end;
    int count;
    SegmentTreeNode left;
    SegmentTreeNode right;
    public SegmentTreeNode(int start, int end) {
        this.start = start;
        this.end = end;
        this.count = 0;
    }
}