315. 计算右侧小于当前元素的个数 （ 归并排序 ）_r语言计算某列小于1的个数

LeetCode： 315. 计算右侧小于当前元素的个数

读完题目后会发现与之前做的某些题变形过来的，解法一样

用 归并排序 分解小问题.

博客指路：

493. 翻转对 （归并排序）

327. 区间和的个数 （归并排序）

还有一题也是变形，待补

题目指路： 剑指 Offer 51. 数组中的逆序对

归并思路：

1. 分分
2. 核心代码 （分解子问题后怎么处理）
3. 合并

解题思路：

1. 归并将数组分割成单个元素不能再分，然后回调两两组合，然后遍历 左区间 计算 右区间小于 左区间当前元素的个数。
2. 然后排序（小到大） >> 可以减少后面遍历的复杂度
3. 在排序后， 如果就使用一个 $int[]arr$ 数组去存每个下标对应的结果个数， 会发现下标与元素对不上号。

比如样例： 给定数组： 2，0，1

第一次组合排序
给定数组： [2，0]，1
结果数组： 2（左区间） > 0 （有区间） >> 1，0，0
排序后变： [0，2]，1

[正确] 这时 index = 0, 这个结果是加到 index = 0 的元素 2 上的

第二次组合排序
给定数组： 0，[2，1]
结果数组： 2（左区间）> 1（右区间） >> 1，1，0
排序后变： 0，[1，2]

[错误] int[] arr：[1,1,0]
[正确] int[] arr：[2,0,0]

这时 index = 1，元素是2，但这个结果应该是加到 index = 0 上的，它加到了 index = 1
因为这个元素 2 本来就是在 index = 0, 只不过是我们需求将它换位了。

4. 所以使用 $class$ lan 记录元素与下标的映射关系，这样排序后就不会找不到正确的下标进行结果的累计

AC Code

class Solution {
    class lan {
        int val;
        int position;
        public lan(int val, int position){
            this.val = val;
            this.position = position;
        }
        public String toString(){
            return "[ "+ position + ": " + val +"]";
        }

    }
    int[] arr ;
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if(nums == null || nums.length == 0) return list;
        int len = nums.length;
        lan[] ma = new lan[len];
        arr = new int[len];
        for (int i = 0; i < len; i++) {
            ma[i] = new lan(nums[i], i);
        }
        divde(0, len - 1, ma);
        for(int i = 0; i < len; i++){
            list.add(arr[i]);
        }
        // System.out.println(Arrays.toString(arr));
        return list;
    }

    public void divde(int start, int end, lan[] nums){
        if(start >= end) return ;
        int mid = start + (end - start) / 2;
        
        // 分
        divde(start, mid, nums);
        divde(mid + 1, end, nums);

        // 核心代码
        int p1 = start;
        while(p1 <= mid){
            int p2 = mid + 1;
            while(p2 <= end && nums[p1].val > nums[p2].val){
                // System.out.println(nums[p1]);
                arr[nums[p1].position]++;
                p2++;
            }
            p1++;
        }

        // 合并
        lan[] temp = new lan[end - start + 1];
        int slow = start, fast = mid + 1;
        int index = 0;
        while(slow <= mid || fast <= end){
            if(slow > mid){
                temp[index++] = nums[fast++];
            } else if(fast > end){
                temp[index++] = nums[slow++];
            } else {
                 if(nums[slow].val < nums[fast].val) {
                    temp[index++] = nums[slow++];
                } else if(nums[slow].val >= nums[fast].val){
                    temp[index++] = nums[fast++];
                }
            }
        }

        // 覆盖
        for(int k = 0; k < index; k++){
            nums[start + k] = temp[k];
        }

    }

}
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

---

leetcode题解： lankerens leetcode题解