leetcode315

2019-11-08 02:08:57

字体：大中小

来源：转载

供稿：网友

该题目是一道典型的分治问题，统计逆序数可以采用经典的mergeAndSort算法实现，但是难点在于如何返回每一个位置的逆序情况。由于sort的时候要交换位置，在此开辟了另一个数组find存储原始映射关系。

再提交过程中，经过三次提交最终AC： 遇到了内存不足的情况，采用vector<> &解决 要关注初始情况。对于nums数组为空时需要单独处理

心得： 由于程序功能比较多，不要一蹴而就，要分几次解决 对于函数返回参数要求比较多的时候，还是python好用啊

代码块

class Solution {public: vector<int> sortAndCount(int left,int right,vector<int>& nums,vector<int>& find,vector<int>& count)// index is from left to right { vector<int> numsLeft; vector<int> numsRight; vector<int> findLeft; vector<int> findRight; find.clear(); if(left!=right) { numsLeft=sortAndCount(left,(left+right)/2,nums,findLeft,count); numsRight=sortAndCount((left+right)/2+1,right,nums,findRight,count); } else { find.push_back(left); numsLeft.push_back(nums[left]); return numsLeft; } return mergeAndSort(numsLeft,numsRight,findLeft,findRight,find,count); } vector<int> mergeAndSort(vector<int>& numsLeft,vector<int>& numsRight,vector<int>& findLeft,vector<int>& findRight,vector<int>& find,vector<int>& count) { int leftIndex=0; int rightIndex=0; vector<int> newsNew; while(leftIndex<numsLeft.size()||rightIndex<numsRight.size()) { if(leftIndex<numsLeft.size()&&rightIndex<numsRight.size()) { if(numsLeft[leftIndex]<=numsRight[rightIndex]) { newsNew.push_back(numsLeft[leftIndex]); find.push_back(findLeft[leftIndex]); count[findLeft[leftIndex]]+=rightIndex; leftIndex++; } else { newsNew.push_back(numsRight[rightIndex]); find.push_back(findRight[rightIndex]); rightIndex++; } } else { if(leftIndex==numsLeft.size()&&rightIndex<numsRight.size()) { newsNew.push_back(numsRight[rightIndex]); find.push_back(findRight[rightIndex]); rightIndex++; } else if(leftIndex<numsLeft.size()&&rightIndex==numsRight.size()) { newsNew.push_back(numsLeft[leftIndex]); find.push_back(findLeft[leftIndex]); count[findLeft[leftIndex]]+=rightIndex; leftIndex++; } else{} } } return newsNew; } vector<int> countSmaller(vector<int>& nums) { vector<int> find; vector<int> result; vector<int> count(nums.size(),0); if(nums.size()==0) return count; else { result=sortAndCount(0,nums.size()-1,nums,find,count); return count; } }};

上一篇：作诗--莫队

下一篇：JVM CMS垃圾回收算法输出的日志格式。

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注