计算右侧小于当前元素的个数(归并排序)

不念不忘少年蓝@ 2022-11-02 16:20 141阅读 0赞

\#\#\# 解题思路

归并排序

\#\#\# 代码

class Solution {
    public:
        vector<int> res;
        vector<pair<int,int>> temp;
        vector<pair<int,int>> pairIdx;
        void mergeSort (vector<pair<int,int>>& nums,int l,int r){
            if(l >= r) return;
            int mid = (l + r) >> 1;
            mergeSort(nums,l,mid);
            mergeSort(nums,mid+1,r);
            int p1=l,p2=mid+1,k=0;
            while(p1 <= mid && p2 <= r){
                if(nums[p1].first <= nums[p2].first){
                    res[nums[p1].second] += p2-mid-1;
                    temp[k++] = nums[p1++];
                }
                else temp[k++] = nums[p2++];
            }
            while(p1 <= mid){
                res[nums[p1].second] += p2-mid-1;
                temp[k++] = nums[p1++];
            }
            while(p2 <= r) temp[k++] = nums[p2++];
            for(int i = l,j=0;i <= r;i++,j++) nums[i] = temp[j];
        }
        vector<int> countSmaller(vector<int>& nums) {
            res = vector<int>(nums.size(),0);
            temp = vector<pair<int,int>>(nums.size());
            for(int i = 0; i < nums.size(); ++i) pairIdx.push_back({nums[i],i});
            mergeSort(pairIdx,0,nums.size()-1);
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关归并排序与自然归并排序

归并排序 > 归并排序(merge - sort)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用.将已有的子序列合并,得到完全有序的序列;

红太狼/ 2024年02月05日 13:52/ 0 赞/ 81 阅读

相关 [Leetcode][第315题][JAVA][计算右侧小于当前元素的个数][暴力][归并排序+索引数组]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

青旅半醒/ 2023年02月25日 07:30/ 0 赞/ 20 阅读

相关 js算法--搜索二维矩阵 II和计算右侧小于当前元素的个数

搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元

末蓝、/ 2022年12月22日 04:40/ 0 赞/ 144 阅读

相关 js算法--计算右侧小于当前元素的个数

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

谁践踏了优雅/ 2022年12月21日 10:54/ 0 赞/ 325 阅读

相关计算右侧小于当前元素的个数(归并排序)

\\\ 解题思路归并排序 \\\ 代码 class Solution { public: vector<int> res;

不念不忘少年蓝@/ 2022年11月02日 16:20/ 0 赞/ 142 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

我就是我/ 2022年10月29日 05:25/ 0 赞/ 181 阅读

相关计算归并排序和快速排序算法排序100-1000个数组的时间（重点在时间精确到微妙us）

//include<sys/time.h> //注意引用这个头文件 //include<unistd.h> include<stdio.h> i

蔚落/ 2022年06月05日 23:28/ 0 赞/ 167 阅读

相关归并类排序-----归并排序

/归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合

绝地灬酷狼/ 2022年05月03日 01:56/ 0 赞/ 298 阅读

相关归并排序——二路归并排序

/ 归并：指将两个或者两个以上的有序表合并成一个新的有序表二路归并算法思想：将长度为n的待排序数据表看

分手后的思念是犯贱/ 2022年03月20日 02:54/ 0 赞/ 359 阅读

相关 matlab计算矩阵中非零元素个数

1、求计算矩阵中每一列非零元素个数假设矩阵A： A = 0 1 0 5 5 6 0 1 9

港控/mmm°/ 2021年10月18日 11:46/ 0 赞/ 1445 阅读