Java Segment Tree solution


  • 0
    F

    // segment tree

        public class Node {
            int start, end;
            int count;
            Node left, right;
            Node(int start, int end){
                this.start = start;
                this.end = end;
            }
        }
        private Node buildTree(int start, int end) {
            if (start > end) return null;
            if (start == end) return new Node(start, end);
            int mid = (start+end)/2;
            Node node = new Node(start, end);
            node.left = buildTree(start, mid);
            node.right = buildTree(mid+1, end);
            return node;
        }
        
        private void update(Node root, int pos) {
            if (root.start == root.end) {root.count++; return;}
            int mid = (root.start+root.end)/2;
            if (pos <= mid) {
                update(root.left, pos);
            } else {
                update(root.right, pos);
            }
            root.count = root.left.count+root.right.count;
        }
        
        private int getCount(Node root, int pos) {
            if (root.start == root.end) return 0;
            int mid = (root.start+root.end)/2;
            int left = 0, right = 0;
            if (pos > mid) {
                right = getCount(root.right, pos);
                left = root.left.count;
            } else {
                left = getCount(root.left, pos);
            }
            return left+right;
        }
        
        public List<Integer> countSmaller(int[] nums) {
            Integer[] count = new Integer[nums.length];
            int[] converts = nums.clone();
            Arrays.sort(converts);
            
            int[] nums2 = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                nums2[i] = Arrays.binarySearch(converts, nums[i]);
            }
    
            Node root = buildTree(0, nums2.length-1);
            
            for (int i = nums.length-1; i >= 0; i--) {
                count[i] = getCount(root, nums2[i]);
                update(root, nums2[i]);
            }
            return Arrays.asList(count);
        }

Log in to reply
 

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