leetcode 315. 计算右侧小于当前元素的个数_给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质:

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

 

题解：

1.一个整数数组

2.计算一个元素在它右侧更小的元素的个数

3.在新数组中相同的位置记录个数

 

示例:

输入: [5,2,6,1]

输出: [2,1,1,0] 

解释:

5 的右侧有 2 个更小的元素 (2 和 1).

2 的右侧仅有 1 个更小的元素 (1).

6 的右侧有 1 个更小的元素 (1).

1 的右侧有 0 个更小的元素.

 

解题思路：

• 在归并排序中，记录各个元素的位置和一个统计个数的数组

• 在归并排序过程中获得一个排完顺序的数组，元素记录的是原数组中元素的下标，按这个下标对应原数组中的元素即是从小到大的顺序

• 因为记录的是右侧的个数，所以在左部分去统计这个个数值

C/C++题解：

class Solution {

public:

    vector<int> keys, vals, tmp;

    vector<int> ret; //记录结果

    vector<int> countSmaller(vector<int>& nums) {

        keys = nums, vals = nums, tmp = nums, ret = nums;

        for (int i = 0; i < nums.size(); i ++) {

            keys[i] = tmp[i] = i; //记录对应下标

            ret[i] = 0;}// 在归并排序过程中一个ret记录下小于的数

        mergeSort(0, nums.size() - 1);

        return ret;}//归并排序

    void mergeSort(int l, int r) {

        if (l >= r) return;//左右指针，左右指针相遇停止

        int m = (l + r) / 2; //取中间

        mergeSort(l, m); //递归左部分

        mergeSort(m + 1, r); //递归右部分

        int i = l, j = m + 1, k = l;

        while (i <= m && j <= r) { //i在左部分，j在右部分

            if (vals[keys[i]] <= vals[keys[j]]) { //比较下标映射值

                ret[keys[i]] += j - m - 1; //左值小了，相应下标记录距离

                tmp[k ++] = keys[i ++];   } //下一个

            else//左值大，右侧有小于当前元素的值

                tmp[k ++] = keys[j ++];}//记下位置,找下一个

        while (i <= m) { //因为是计算右侧的，所以写在左部分

            ret[keys[i]] += j - m - 1;//计算个数

            tmp[k ++] = keys[i ++]; }

        while (j <= r) //右部分统一位置

            tmp[k ++] = keys[j ++];

        for (int i = l; i <= r; i ++)

            keys[i] = tmp[i];}};//再从左到右重新更新

Debug结果：

Java题解：

class Solution {

    public int[] keys, vals, tmp, ret;

    public List<Integer> countSmaller(int[] nums) {

        keys = nums.clone(); vals = nums.clone();

        tmp = nums.clone(); ret = nums.clone();

        for (int i = 0; i < nums.length; i ++) {

            keys[i] = tmp[i] = i; //记录对应下标

            ret[i] = 0;}// 在归并排序过程中一个ret记录下小于的数

        mergeSort(0, nums.length - 1);

        return Arrays.stream(ret).boxed().collect(Collectors.toList());

    }//归并排序

    public void mergeSort(int l, int r) {

        if (l >= r) return;//左右指针，左右指针相遇停止

        int m = (l + r) / 2; //取中间

        mergeSort(l, m); //递归左部分

        mergeSort(m + 1, r); //递归右部分

        int i = l, j = m + 1, k = l;

        while (i <= m && j <= r) { //i在左部分，j在右部分

            if (vals[keys[i]] <= vals[keys[j]]) { //比较下标映射值

                ret[keys[i]] += j - m - 1; //左值小了，相应下标记录距离

                tmp[k ++] = keys[i ++];}  //下一个

            else//左值大，右侧有小于当前元素的值

                tmp[k ++] = keys[j ++]; }//记下位置,找下一个

        while (i <= m) { //因为是计算右侧的，所以写在左部分

            ret[keys[i]] += j - m - 1;//计算个数

            tmp[k ++] = keys[i ++];}

        while (j <= r) //右部分统一位置

            tmp[k ++] = keys[j ++];

        for ( i = l; i <= r; i ++)

            keys[i] = tmp[i];}};//再从左到右重新更新

Debug结果：

Python题解：

class Solution(object):

    def countSmaller(self, nums):

        """:type nums: List[int]:rtype: List[int] """

        def mergeSort(l, r):

            if l >= r: return #左右指针，左右指针相遇停止

            m = (l + r) / 2 #取中间

            mergeSort(l, m) #递归左部分

            mergeSort(m + 1, r) #递归右部分

            i, j, k = l, m + 1, l

            while i <= m and j <= r: #i在左部分，j在右部分

                if vals[keys[i]] <= vals[keys[j]]: #比较下标映射值

                    ret[keys[i]] += j - m - 1 #左值小了，相应下标记录距离

                    tmp[k] = keys[i] #下一个

                    k, i = k+1, i+1

                else: #左值大，右侧有小于当前元素的值

                    tmp[k] = keys[j] #记下位置,找下一个

                    k, j = k+1, j+1

            while i <= m: #因为是计算右侧的，所以写在左部分

                ret[keys[i]] += j - m - 1 #计算个数

                tmp[k] = keys[i]

                k, i = k+1, i+1

            while j <= r: #右部分统一位置

                tmp[k] = keys[j]

                k, j = k+1, j+1

            for i in range(l, r+1):

                keys[i] = tmp[i] #再从左到右重新更新

        keys, vals = nums[:], nums[:]

        tmp, ret = nums[:], nums[:]

        keys = [i for i in range(len(nums))]

        tmp = [i for i in range(len(nums))]

        ret = [0 for _ in range(len(nums))]

        #在归并排序过程中一个ret记录下小于的数

        mergeSort(0, len(nums) - 1)

        return ret

Debug结果：

更多题解移步公众号免费获取