已知數組nums，求新數組count，count[i]代表了在nums[i]右側且比 nums[i]小的元素個數。

例如:
nums = [5, 2, 6, 1], count = [2, 1, 1, 0];
nums = [6, 6, 6, 1, 1, 1], count = [3, 3, 3, 0, 0, 0];
nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];

這個問題的尋找過程如下:
對于nums數組[5,2,6,1]中：
對于nums[0]=5，其后面比他小的元素有兩個，則count[0]=2
對于nums[1]=2，其后面比她小的元素有一個，則count[1]=1
…

此時，一個比較普通但是時間復雜度較高（O(n^2)）的算法實現即為先排序，再一個一個元素遍歷，構造count數組。

但是我們直到分治算法的過程時間復雜度為(O(nlogn))，那可不可以嘗試一下使用歸并的過程構建count數組。

分治算法的步驟：

1. 分解，將要解決的問題劃分成若 干規模較小的同類問題;
2. 求解，當子問題劃分得足夠小時 ，用較簡單的方法解決;
3. 合并，按原問題的要求，將子問題 的解逐層合并構成原問題的解。

分解：
我們要構造count數組，假如這個數組 被分為兩個有序的數組
nums: [-7 1 5 9],[-2 1 3 5]
假設：
nums1[-7 1 5 9]， 下標從i開始
nums2[-2 1 3 5]， 下標從j開始
進行合并兩個有序鏈表的過程：
i =0, j= 0, nums[i] = -7時，count[i] = 0
num1[i] < nums2[j], i++
對于i=1,j=0,count[i] = 1

nums1[i] > nums2[j], j++
此時i=1,j=1,count[i] = 1

…

綜合上面的過程，我們能夠發現，對于count1[i] ，它總是等于同一時刻j的數值
即count[0] = 0, count[1] =1, count[2] = 3;

此時我們能夠對以上逆序數組通過歸并排序進行構造：

/*pair<int,int> first元素保存當前數組的值，second元素保存當前元素的下標*/void merge_two_arr(std::vector<pair<int,int>> &arr1, std::vector<pair<int,int>> &arr2, std::vector<pair<int,int>> &result,std::vector<int> &count) {int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) {if (arr1[i].first <= arr2[j].first) { //歸并的篩選條件/*對于此時的arr[i]的元素，它的count值為上一個j所代表的數值因為之前的arr2[j]以及比它小的元素肯定比當前的arr[i]小。*/count[arr1[i].second] += j; result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {//對于剩余的元素做同樣的處理for (;i < arr1.size(); ++i) {count[arr1[i].second] += j;result.push_back(arr1[i]);}}
}

測試代碼如下:

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;/*
已知數組nums，求新數組count，count[i]代表了在nums[i]右側且比 nums[i]小的元素個數。
例如:
nums = [5, 2, 6, 1], count = [2, 1, 1, 0];
nums = [6, 6, 6, 1, 1, 1], count = [3, 3, 3, 0, 0, 0];
nums = [5, -7, 9, 1, 3, 5, -2, 1], count = [5, 0, 5, 1, 2, 2, 0, 0];
*//**/
void merge_two_arr(std::vector<pair<int,int>> &arr1,std::vector<pair<int,int>> &arr2,std::vector<pair<int,int>> &result,std::vector<int> &count) {int i = 0;int j = 0;while(i < arr1.size() && j < arr2.size()) {if (arr1[i].first <= arr2[j].first) {count[arr1[i].second] += j;result.push_back(arr1[i]);i++;} else {result.push_back(arr2[j]);j++;}}if (i == arr1.size()) {for (;j < arr2.size(); ++j) {result.push_back(arr2[j]);}} else {for (;i < arr1.size(); ++i) {count[arr1[i].second] += j;result.push_back(arr1[i]);}}
}/*歸并排序*/
void merge_sort(std::vector<pair<int,int>> &arr, std::vector<int> &count) {if (arr.size() < 2) {return ;}int mid = arr.size() / 2;std::vector<pair<int,int>> arr1;std::vector<pair<int,int>> arr2;for (int i = 0; i < mid; ++i) {arr1.push_back(arr[i]);}for (int i = mid; i< arr.size(); ++i){arr2.push_back(arr[i]);}/*分治*/merge_sort(arr1, count);merge_sort(arr2, count);arr.clear();/*求解*/merge_two_arr(arr1,arr2,arr,count);
}int main(int argc, char const *argv[])
{std::vector<pair<int,int>> arr;std::vector<int> count;int n;int tmp;cin >> n;for (int i = 0;i < n; ++i) {cin >> tmp;arr.push_back(make_pair(tmp,i));count.push_back(0);}merge_sort(arr, count);for (int i = 0;i < count.size(); ++i) {cout << count[i] << " ";}cout << endl;return 0;
}

最終輸出如下:

#輸入
8
5 -7 9 1 3 5 -2 1
#輸出
5 0 5 1 2 2 0 0 

總結

以上是生活随笔為你收集整理的递归/归并：count of smaller numbers求逆序数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。