leetcode315

2019-11-08 02:08:57

字體：大中小

供稿：網(wǎng)友

該題目是一道典型的分治問題，統(tǒng)計(jì)逆序數(shù)可以采用經(jīng)典的mergeAndSort算法實(shí)現(xiàn)，但是難點(diǎn)在于如何返回每一個(gè)位置的逆序情況。由于sort的時(shí)候要交換位置，在此開辟了另一個(gè)數(shù)組find存儲原始映射關(guān)系。

再提交過程中，經(jīng)過三次提交最終AC： 遇到了內(nèi)存不足的情況，采用vector<> &解決 要關(guān)注初始情況。對于nums數(shù)組為空時(shí)需要單獨(dú)處理

心得： 由于程序功能比較多，不要一蹴而就，要分幾次解決 對于函數(shù)返回參數(shù)要求比較多的時(shí)候，還是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; } }};

上一篇：作詩--莫隊(duì)

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