[Java] Accept by using segment tree


  • 0
    S

    public class Solution {
    //SegmentTree or BIT
    static class SegmentNode {
    int l, r, count;
    SegmentNode lc, rc;

        SegmentNode(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
    
    public int reversePairs(int[] nums) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        TreeSet<Long> set = new TreeSet<>();
        for (int num : nums) {
            set.add((long) num);
        }
        long[] sortNums = new long[set.size()];
        HashMap<Long, Integer> idxMap = new HashMap<>();
        int idx = 0;
        for (long num : set) {
            sortNums[idx] = num;
            idxMap.put(num, idx++);
        }
        SegmentNode root = buildTree(0, idx - 1);
    
        int result = 0;
        for (int i = 0; i < nums.length; ++i) {
            long num = nums[i] * 2L + 1;
            int index = Arrays.binarySearch(sortNums, num);
            if (index < 0) {
                index = -(index + 1);
            }
            result += getCount(index, idxMap.size() - 1, root);
            update(idxMap.get((long) nums[i]), root);
        }
        return result;
    }
    
    private SegmentNode buildTree(int l, int r) {
        if (l == r) {
            return new SegmentNode(l, r);
        }
        SegmentNode cur = new SegmentNode(l, r);
        int mid = l + (r - l) / 2;
        cur.lc = buildTree(l, mid);
        cur.rc = buildTree(mid + 1, r);
        return cur;
    }
    
    private int getCount(int l, int r, SegmentNode node) {
        if (node == null || node.l > r || node.r < l) {
            return 0;
        }
        if (l == node.l && r == node.r) {
            return node.count;
        }
        int mid = node.l + (node.r - node.l) / 2;
        if (mid >= r) {
            return getCount(l, r, node.lc);
        } else if (mid < l) {
            return getCount(l, r, node.rc);
        } else {
            return getCount(l, mid, node.lc) + getCount(mid + 1, r, node.rc);
        }
    }
    
    private void update(int idx, SegmentNode node) {
        if (node.l <= idx && node.r >= idx) {
            node.count++;
        } else {
            return;
        }
        if (node.l == node.r) {
            return;
        }
        update(idx, node.lc);
        update(idx, node.rc);
    }
    

    }


Log in to reply
 

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