本篇前提條件是已學會歸并排序
1、排序數(shù)組
912. 排序數(shù)組
排序數(shù)組也可以用歸并排序來做。
vector<int> tmp;//寫成全局是因為如果在每一次小的排序中都創(chuàng)建一次，更消耗時間和空間，設置成全局的就更高效
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) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
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、數(shù)組中的逆序對
劍指 Offer 51. 數(shù)組中的逆序對
如果暴力枚舉，一定是可以解決問題的，但肯定不用這個解法。選擇逆序對，可以先把數(shù)組分成兩部分，左半部分 + 右半部分的逆序對，以及再找左半部分的數(shù)字和右半部分數(shù)字成對的數(shù)，比如上面例子中，7和6，7和4就是這種情況。左 + 右 + 一左一右就是整體的逆序對數(shù)量。當這兩半部分都處理完后，就擴大區(qū)間，繼續(xù)上述操作。這個解法也就是利用歸并排序，歸并排序的思路就是劃分到最小的區(qū)間，只有1個數(shù)，它一定是有序的，回到上一層，也就是2個數(shù)的區(qū)間，讓它們排好序，在它右邊的也是2個數(shù)的區(qū)間，重復和它一樣的操作，這樣兩個區(qū)間都有序后，再往上走一層，來到4個數(shù)的區(qū)間，4個數(shù)，每一半都是有序的，將整體的4個數(shù)排成有序的，再往上走，來到8個數(shù)的區(qū)間，重復操作。
利用歸并排序的思路，我們在兩個區(qū)間都排成升序后，定義兩個指針cur指向兩個區(qū)間的開頭，然后一左一右比較大小，如果cur1比cur2大，那么cur1之后都比cur2大，就可以一次性加上多個逆序對的個數(shù)。
下面的代碼可以從最小的區(qū)間開始一個個代入來理解。從只有2個數(shù)的區(qū)間開始，走到遞歸處，分成2個只有1個數(shù)的區(qū)間，那就會返回0，兩處遞歸走完，來到下面的循環(huán)，此時left是0，right是1，mid是0，帶入進去會發(fā)現(xiàn)，最后的ret只會是0或者1，并且這2個數(shù)也在最后排好序了，返回后，來到上一層，也就是走左邊遞歸的那行代碼，然后再走右邊，也是2個數(shù)，也是同樣的操作，2個區(qū)間排好序了，4個數(shù)的區(qū)間就一左一右比較大小，找出逆序對，排好序，再走到上一層，8個數(shù)的區(qū)間也是如此。
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;
//1. 找中間點，將數(shù)組分成兩部分
int mid = (left + right) >> 1;
// [left, mid] [mid + 1, right]
//2. 左邊個數(shù) + 排序 + 右邊個數(shù) + 排序
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
//3. 一左一右的個數(shù)
int cur1 = left, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)//while體內(nèi)原本是歸并排序的代碼，現(xiàn)在就多加一點
{
if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
else
{
ret += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
//4. 處理排序
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、計算右側小于當前元素的個數(shù)
315. 計算右側小于當前元素的個數(shù)
此題和上一個題有相同之處，也是分治，也是利用歸并排序，這道題可以看作，當前元素后面，有多少比我小的，而上一題則是當前元素前面，有多少比我大的。仔細想一想，上一題是排升序，這一題排降序則更為合適。這題和上一題還有不同的地方。
cur1和cur2，排成降序，如果cur1 <= cur2，cur2++，因為我們要找比當前元素小的；如果cur1 > cur2，由于是降序，那么cur2之后的肯定都小，但這里不能加上ret，我們要返回一個數(shù)組，要把這個數(shù)加在當前元素的原始下標，因為數(shù)組已經(jīng)被我們給排序了，所以要找原始下標。這里的做法就是從最一開始就除了tmp外，再定義一個數(shù)組，存儲著原始下標，因為這時候還沒開始排序，可以找得到，然后每次原數(shù)組元素變換位置，這個下標數(shù)組也跟著變換。
我們要定義四個數(shù)組，一個是結果數(shù)組，一個是原始下標數(shù)組，一個是輔助數(shù)組，也就是tmp，記錄改動過的順序，一個是下標輔助數(shù)組，記錄改動后的下標順序。在while循環(huán)中，每次更新tmp，下標輔助數(shù)組也跟著更新。如果cur1大于cur2，那么除了更新，還需要往結果數(shù)組中寫入個數(shù)，要在當前元素的原始下標處寫入個數(shù)，這里最好要畫圖來理解，畫原始下標和下標變動后的圖。在最后for循環(huán)中的排序，除了原數(shù)組nums，還有原始下標數(shù)組也要排序。
vector<int> index;//原始元素下標
vector<int> res;//最終結果
int tmp[500010];//排序輔助數(shù)組
int tmpIndex[500010];//元素下標的輔助數(shù)組
public:
vector<int> countSmaller(vector<int>& nums) {
int sz = nums.size();
index.resize(sz);
res.resize(sz);
for(int i = 0; i < sz; i++)
{
index[i] = i;
}
mergeSort(nums, 0, sz - 1);
return res;
}
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, cur2 = mid + 1, i = 0;
while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] <= nums[cur2])
{
tmp[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
else
{
res[index[cur1]] += right - cur2 + 1;//經(jīng)歷了之前的排序，index已經(jīng)記錄下了最新的下標變動，這里就可以直接用cur1來獲取正確的下標
tmp[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
while(cur1 <= mid)
{
tmp[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while(cur2 <= right)
{
tmp[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for(int j = left; j <= right; j++)
{
nums[j] = tmp[j - left];
index[j] = tmpIndex[j - left];
}
}
4、翻轉對
493. 翻轉對
還是一樣的思路。左半部分，右半部分，然后一左一右。不過這里的條件不一樣。這里的解決辦法有兩個，一個是計算當前元素后面有多少元素的兩倍比我小，另一個是計算當前元素之前，有多少元素的一半比我大，這兩個的高效順序分別是降序和升序。
第一個思路，cur1和cur2，找當前元素的后面，那就以cur1為重點，如果cur2的2倍大于等于cur1，cur2就往后走，如果小于，那么后面的肯定都小于。第二個思路，cur1和cur2，找當前元素的前面，那就以cur2為重點，如果cur1的一半比cur2小，那么cur1后的肯定都符合條件，如果cur1的一半大于cur2，那cur1往后走。最后合并兩個有序數(shù)組。文章來源：http://www.zghlxwxcb.cn/news/detail-690575.html
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 cur1 = left, cur2 = mid + 1, i = left;//先計算翻轉對，0還是left都行
/*while(cur1 <= mid)//這里排降序，也可以排升序
{
while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;//2.0是為了防止除不盡
if(cur2 > right) break;
ret += right - cur2 + 1;
cur1++;
}*/
while(cur2 <= right)//升序
{
while(cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0) cur1++;
if(cur1 > mid) break;
ret += mid - cur1 + 1;
cur2++;
}
cur1 = left, cur2 = mid + 1;//歸位一下，開始排序
while(cur1 <= mid && cur2 <= right)
{
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
//tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : 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];
}
return ret;
}
結束。文章來源地址http://www.zghlxwxcb.cn/news/detail-690575.html
到了這里，關于C++算法 —— 分治（2）歸并的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
