LeetCode[315]计算右侧小于当前元素的个数-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode[315]计算右侧小于当前元素的个数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

难度：Hard

题目：

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

重点！！！解题思路

明确解题思路：

题中要求求出右侧小于当前元素的数量，如果将数组拆分开来，左右两边都是降序排列，如果当左边数组有一个值大于右边数组的其中一个值，那么就意味着比当前左边这个数小的元素有右边那个数到右边数组末尾那么多个，即题目可使用归并排序来解决。

源码+讲解：

    class Solution {
        class Data {  //因为你要记录每个值所对应得右边元素个数，hashmap太麻烦，我们直接封装一个内部类
            int ind, val, cnt;  //对应下标，值，右边对应得元素

            public Data(int ind, int val) {  //初始化
                this.ind = ind;
                this.val = val;
                cnt = 0;
            }
        }

        Data[] temp;  //归并排序的克隆数组

        public List<Integer> countSmaller(int[] nums) {
            temp = new Data[nums.length];
            Data[] data = new Data[nums.length];  //待排序数组
            for (int i = 0; i < nums.length; i++) {  //将每个元素封装到类中
                data[i] = new Data(i, nums[i]);
            }
            merge_sort(data, 0, data.length - 1);  //开始归并排序
            Arrays.sort(data, new Comparator<Data>() {  //当归并排序后，我们需要每个数组下标从小到大来输出，那么我们就需要一个小顶堆
                @Override
                public int compare(Data o1, Data o2) {
                    return o1.ind - o2.ind;
                }
            });
            List<Integer> res = new ArrayList<>();  //集合结果用来还原堆中的值
            for (Data datum : data) {
                res.add(datum.cnt);
            }
            return res;
        }

        //很基础的一个归并排序解法 如果有不懂得朋友 可以看看我前面发的题
        public void merge_sort(Data[] data, int l, int r) {
            if (l >= r) return;
            int mid = (l + r) >> 1;
            merge_sort(data, l, mid);
            merge_sort(data, mid + 1, r);
            int k = l, p1 = l, p2 = mid + 1;
            while (p1 <= mid || p2 <= r) {
                if (p2 > r || (p1 <= mid && data[p1].val > data[p2].val)) {
                    data[p1].cnt+=(r-p2+1);
                    temp[k++] = data[p1++];
                } else {
                    temp[k++] = data[p2++];
                }
            }
            for (int i=l;i<=r;i++) data[i]=temp[i];
        }
    }

运行结果：

LeetCode[315]计算右侧小于当前元素的个数,算法刷题篇,快速排序,# 归并排序(Merge-Sort):从二路到多路,leetcode,算法,排序算法