1、排序數組

class Solution 
{vector<int> tmp;
public:vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());mergeSort(nums,0,nums.size() - 1);return nums;}void mergeSort(vector<int>& nums, int left , int right){if(left >= right) return;int mid = (left + right) >> 1;mergeSort(nums,left, mid);mergeSort(nums,mid + 1, right);int cur1 = left;int cur2 = mid+1;int i = 0;while((cur1 <= mid)&&(cur2 <= right)){if(nums[cur1]>nums[cur2]){tmp[i++] =  nums[cur2++];}else{tmp[i++] = nums[cur1++];}}while(cur1 <= mid){tmp[i++] = nums[cur1++];}while(cur2 <= right){tmp[i++] = nums[cur2++];}for(int i = left; i <= right;i++){nums[i] = tmp[i - left];}}
};

?2、數組中的逆序對

（2）解題思路

方法一：暴力解法，一個一個的尋找，雖然可以找到，但是會超時

方法二：歸并

我們可以先找左邊部分的逆序對，再找右半部分逆序對，最后再找一左一右的，如果我們可以找的途中還能排序，會使最后一步非常的簡單 變成了 左半部分 -》左排序 -》右半部分 -》右排序 -》一左一右，這和歸并算法的思想差不多

class Solution 
{int tmp[50010];
public:int reversePairs(vector<int>& nums) {return mergeSort(nums,0,nums.size() - 1);}int mergeSort(vector<int>& nums, int left, int right){if(left>=right) return 0;int ret = 0;int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int i = 0;int cur1 = left;int cur2 = mid + 1;while(cur1 <=  mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur1++];}else{ret +=  mid - cur1 + 1;tmp[i++] = nums[cur2++];}}while(cur1<=mid){tmp[i++] = nums[cur1++];}while(cur2<=right){tmp[i++] = nums[cur2++];}for(int j = left; j<=right; j++){nums[j] = tmp[j -left];}return ret;}
};

3、計算右側小于當前元素的個數

方法一：暴力解法

方法二：和上述的算法差不多,先算左邊的數,在算右邊的數,再算左右兩邊,右側小于當前元素的個數

class Solution 
{vector<int> tmp;vector<int> init;vector<int> ret;vector<int> tmpinit;
public:vector<int> countSmaller(vector<int>& nums) {tmp.resize(size(nums));init.resize(size(nums));ret.resize(size(nums));tmpinit.resize(size(nums));for(int i = 0; i<nums.size();i++){init[i] = i;}mergeSort(nums,0,nums.size() - 1);return ret;}void mergeSort(vector<int>& nums, int left , int right){if(left>=right){return ;}int mid = (left + right)>>1;mergeSort(nums,left,mid);mergeSort(nums, mid+1,right);int cur1 = left;int cur2 = mid+1;int i =0;while(cur1<=mid && cur2<=right){if(nums[cur1]>nums[cur2]){ret[init[cur1]]+= right - cur2 +1;tmp[i] = nums[cur1];tmpinit[i++] = init[cur1++];  }else{tmp[i] = nums[cur2];tmpinit[i++] = init[cur2++];  }}while(cur1<=mid){tmp[i] = nums[cur1];tmpinit[i++] = init[cur1++];  }while(cur2<=right){tmp[i] = nums[cur2];tmpinit[i++] = init[cur2++];  }for(int i = left ; i <= right; i++){nums[i] = tmp[i-left];init[i] = tmpinit[i-left];}}
};

5、翻轉對

class Solution 
{vector<int> tmp;
public:int reversePairs(vector<int>& nums) {tmp.resize(size(nums));return mergeSort(nums,0,nums.size()-1);}int mergeSort(vector<int>& nums, int left, int right){int ret = 0;if(left>=right) return 0;int mid = (left + right) >> 1;ret += mergeSort(nums,left,mid);ret += mergeSort(nums,mid+1,right);int cur1 = left; int cur2 = mid+1;int i = 0;while(cur1<=mid){while(cur2<=right&&nums[cur2]>=nums[cur1]/2.0)cur2++;if(cur2 > right)break;ret += right - cur2 +1;cur1++;} cur1 = left;cur2 = mid + 1;while(cur1 <=  mid && cur2 <= right){if(nums[cur1] <= nums[cur2]){tmp[i++] = nums[cur2++];}else{tmp[i++] = nums[cur1++];}}while(cur1<=mid){tmp[i++] = nums[cur1++];}while(cur2<=right){tmp[i++] = nums[cur2++];}for(int j = left; j<=right; j++){nums[j] = tmp[j -left];}return ret;}
};