Share 4 Java Solutions.


  • 0
    M

    Segment Tree:

    public class Solution {
        private class SegTreeNode{
            SegTreeNode left, right;
            int count;
            int lo, hi;
            public SegTreeNode(int lo, int hi, int cnt) {
                this.lo = lo;
                this.hi = hi;
                this.count = cnt;
            }
        }
        private SegTreeNode build(int start, int end) {
            if (start > end) return null;
            SegTreeNode root = new SegTreeNode(start, end, 0);
            if (start == end) return root;
            int mid = start + (end - start) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
            return root;
        }
        private void update(SegTreeNode root, int ind, int value) {
            if (root.lo == root.hi && root.lo == ind) {
                root.count += value;
                return;
            }
            int mid = root.lo + (root.hi - root.lo) / 2;
            if (ind >= root.lo && ind <= mid) {
                update(root.left, ind, value);
            } else if(ind <= root.hi) {
                update(root.right, ind, value);
            }
            root.count = root.left.count + root.right.count;
        }
        private int query(SegTreeNode root, int start, int end) {
            if (start > end || root == null || end < root.lo || start > root.hi) return 0;
            if (root.lo == start && root.hi == end) return root.count;
            int cnt = 0;
            int mid = root.lo + (root.hi - root.lo) / 2;
            if (start <= mid) cnt += query(root.left, start, Math.min(end, mid));
            if (end > mid) cnt += query(root.right, Math.max(mid + 1, start), end);
            return cnt;
        }
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> list = new LinkedList<>();
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int i : nums) {
                min = Math.min(min, i);
                max = Math.max(max, i);
            }
            SegTreeNode root = build(min, max);
            
            for (int i = nums.length - 1; i >= 0; --i) {
                list.add(0, query(root, min, nums[i] - 1));
                update(root, nums[i], 1);
            }
            return list;
        }
    }
    

    Binary Indexed Tree:

    public class Solution {
        private class BIT {
            int[] bit;
            public BIT(int size) {
                bit = new int[size + 1];
            }
            public void increase(int i, int diff) {
                while (i < bit.length) {
                    ++bit[i];
                    i += (i & -i);
                }
            }
            public int query(int i) {
                int count = 0;
                while (i > 0) {
                    count += bit[i];
                    i -= (i & -i);
                }
                return count;
            }
        }
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> list = new LinkedList<>();
            if (nums == null || nums.length == 0) return list;
            int n = nums.length;
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            for (int i : nums) {
                max = Math.max(max, i);
                min = Math.min(min, i);
            }
            BIT bit = new BIT(max - min + 1);
            for (int i = n - 1; i >= 0; --i) {
                list.add(0, bit.query(nums[i] - min));
                bit.increase(nums[i] - min + 1, 1);
            }
            return list;
        }
    }
    

    Merge Sort / Divide and Conquer :

    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            List<Integer> list = new ArrayList<>();
            if (nums == null || nums.length == 0) return list;
            int n = nums.length;
            int[] inds = new int[n], cnt = new int[n];
            for (int i = 0; i < n; ++i) inds[i] = i;
            mergeSort(nums, inds, cnt, 0, n - 1);
            for (int i : cnt) list.add(i);
            return list;
        }
        private void mergeSort(int[] nums, int[] inds, int[] cnt, int lo, int hi) {
            if (lo >= hi) return;
            int mid = lo + (hi - lo) / 2;
            mergeSort(nums, inds, cnt, lo, mid);
            mergeSort(nums, inds, cnt, mid + 1, hi);
            merge(nums, inds, cnt, lo, hi);
        }
        private void merge(int[] nums, int[]inds, int[]cnt, int lo, int hi) {
            if (lo >= hi) return;
            int mid = lo + (hi - lo) / 2;
            int l = lo, r = mid + 1;
            int rCnt = 0;
            int[] tempInds = new int[hi - lo + 1];
            int ind = lo;
            while (l <= mid || r <= hi) {
                if (l <= mid && r <= hi && nums[inds[l]] > nums[inds[r]] || l > mid) {
                    tempInds[ind - lo] = inds[r];
                    ++ind;
                    ++r;
                    ++rCnt;
                } else {
                    tempInds[ind - lo] = inds[l];
                    cnt[inds[l]] += rCnt;
                    ++ind;
                    ++l;
                }
            }
            for (int i = lo; i <= hi; ++i) {
                inds[i] = tempInds[i - lo];
            }
        }
    }
    

    Binary Search Tree :

    public class Solution {
        private class BST{
    		BST left, right;
    		int val;
    		int cnt = 1;
    		int leftCnt = 0;
    		public BST(int value) {
    			val = value;
    		}
    	}
    	private BST insert(BST root, int x) {
    		if (root == null) return new BST(x);
    		if (root.val == x) {
    			++root.cnt;
    			return root;
    		}
    		if (x < root.val) {
    			++root.leftCnt;
    			root.left = insert(root.left, x);
    		} else {
    			root.right = insert(root.right, x);
    		}
    		return root;
    	}
    	private int query(BST root, int x, int pre) {
    		if (root == null) return pre;
    		if (root.val == x) return pre + root.leftCnt;
    		if (x < root.val) return query(root.left, x, pre);
    		return query(root.right, x, pre + root.cnt + root.leftCnt);
    	}
    	
    	public List<Integer> countSmaller(int[] nums) {
    		List<Integer> list = new LinkedList<>();
    		if (nums == null || nums.length == 0) return list;
    		int n = nums.length;
    		BST tree = new BST(nums[n - 1]);
    		list.add(0, 0);
    		for (int i = n - 2; i >= 0; --i) {
    			list.add(0, query(tree, nums[i], 0));
    			insert(tree, nums[i]);
    		}
    		return list;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.