LeetCode 315. 计算右侧小于当前元素的个数_public list countsmaller(int[] nums) { }

//解法一：分治 用额外的index数组记录下标 根据index归并排序并计算答案 有点慢我日
class Solution {
    int[] res;
    int[] tmp;
    int[] index;
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        res = new int[n];
        tmp = new int[n];
        index = new int[n];
        for(int i = 0; i < n; i++)
            index[i] = i;
        merge(nums, 0, n - 1);
        List<Integer> list = new ArrayList<Integer>();
        for(int num : res){
            list.add(num);
        }
        return list;
    }

    public void merge(int[] a, int l, int r){
        if(l == r)
            return;
        int mid = l + r >> 1;
        merge(a, l, mid);
        merge(a, mid + 1, r);
        if(a[index[mid]] <= a[index[mid + 1]])
            return;
        
        //合并
        for(int i = l; i <= r; i++)
            tmp[i] = index[i];
        int i = l;
        int j = mid + 1;
        for(int k = l; k <= r; k++){
            if(i > mid){
                index[k] = tmp[j++];
            }else if(j > r){
                index[k] = tmp[i++];
                res[index[k]] += (r - mid);
            }else{
                if(a[tmp[i]] <= a[tmp[j]]){
                    index[k] = tmp[i++];
                    res[index[k]] += j - mid - 1;
                }else{
                    index[k] = tmp[j++];
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

//解法二：树状数组 慢。。。。
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        int len = nums.length;
        if(len == 0) return res;
        //将nums中的元素排序，记录每个元素对应的索引
        TreeSet<Integer> set = new TreeSet();
        for(int i = 0; i < len; i++){
            set.add(nums[i]);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int index = 1;
        for(Integer n : set){
            map.put(n, index);
            index++;
        }
        //利用索引更新并统计
        FenwickTree fenwickTree = new FenwickTree(len + 1);
        for(int i = len - 1; i >= 0; i--){
            index = map.get(nums[i]);
            //在索引位置添加计数1
            fenwickTree.update(index, 1);
            //统计比索引对应元素小的个数
            res.addFirst(fenwickTree.query(index - 1));
        }
        return res;
    }

    //线段树，O(logn)实现单点更新和前缀和计算
    private class FenwickTree {

        private int[] tree;
        private int len;

        public FenwickTree(int n) {
            this.len = n;
            tree = new int[n + 1];
        }
        //更新本节点和父节点
        public void update(int i, int delta) {
            while (i <= this.len) {
                tree[i] += delta;
                i += lowbit(i);
            }
        }
        //求和，找到对应树的节点
        public int query(int i) {
            int sum = 0;
            while (i > 0) {
                sum += tree[i];
                i -= lowbit(i);
            }
            return sum;
        }
        //计算第一个非0的位置，2的幂
        public int lowbit(int x) {
            return x & (-x);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

//解法三：线段树 也慢。。。
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        LinkedList<Integer> res = new LinkedList<>();
        int len = nums.length;
        if(len == 0) return res;
        //获取区间范围
        int start = nums[0], end = nums[0];
        for(int i = 0; i < len; i++){
            if(nums[i] < start) start = nums[i];
            if(nums[i] > end) end = nums[i];
        }
        //构建树
        SegmentTreeNode root = build(start, end);
        //从右向左，边插入边计数
        for(int i = len - 1; i >= 0; i--){
            //计数小于该元素的区间，所以要减一
            res.addFirst(count(root, start, nums[i] - 1));
            insert(root, nums[i], 1);
        }
        return res;
    }
    //线段树节点，包含左右最值和该区间叶子节点数，子区间不断递减
    private class SegmentTreeNode{
        int start, end, count;
        SegmentTreeNode left, right;

        public SegmentTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            this.count = 0;
            left = null;
            right = null;
        }
    }
    //构建线段树，不断递减区间长度
    private SegmentTreeNode build(int start, int end){
        if(start > end) return null;
        SegmentTreeNode root = new SegmentTreeNode(start, end);
        if(start != end){
            int mid = start + (end - start) / 2;
            root.left = build(start, mid);
            root.right = build(mid + 1, end);
        }
        return root;
    }
    //插入并更新叶子节点
    private void insert(SegmentTreeNode root, int index, int val){

        if (root.start == index && root.end == index){
            root.count += val;
            return;
        }

        int mid = root.start + (root.end - root.start) / 2;
        if (index >= root.start && index <= mid)
            insert(root.left, index, val);
        if (index > mid && index <= root.end)
            insert(root.right, index, val);
        //更新父节点的统计数，便于正好落在区间上的查找
        root.count = root.left.count + root.right.count;
    }
    //根据区间统计
    private int count(SegmentTreeNode root, int start, int end){
        //nums[i] - 1, 排除相等的情况
        if(start > end) return 0;
        //递归到叶子节点，获取计数值
        if (start == root.start && end == root.end){
            return root.count;
        }
        int mid = root.start + (root.end - root.start) / 2;
        int leftcount = 0, rightcount = 0;
        //统计左半区
        if (start <= mid){
            if (mid < end)
                leftcount = count(root.left, start, mid);
            else
                leftcount = count(root.left, start, end);
        }
        //统计右半区
        if (mid < end){
            if (start <= mid)
                rightcount = count(root.right, mid + 1, end);
            else
                rightcount = count(root.right, start, end);
        }
        return (leftcount + rightcount);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89