当前位置:   article > 正文

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

给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: c

给定一个整数数组 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结果:

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/87082
推荐阅读
相关标签
  

闽ICP备14008679号