【归并算法】排序数组 / LCR 生意业务逆序对的总数 / 盘算右侧小于当前元素的个数 / 翻转对

   ⭐️个人主页：@小羊    ⭐️所属专栏：排序算法    很荣幸您能阅读我的文章，诚请品评辅导，欢迎欢迎 ~

---

排序数组

• 排序数组
  

1. class Solution {
2.     vector<int> tmp;
3. public:
4.     vector<int> sortArray(vector<int>& nums) {
5.         int sz = nums.size();
6.         tmp.resize(sz);
7.         MergeSort(nums, 0, sz - 1);
8.         return nums;
9.     }
10.     void MergeSort(vector<int>& arr, int l, int r)
11.     {
12.         if (l >= r) return;
13.         int mid = (l + r) >> 1;
14.         MergeSort(arr, l, mid);
15.         MergeSort(arr, mid + 1, r);
16.         int b1 = l, b2 = mid + 1, i = l;
17.         while (b1 <= mid && b2 <= r)
18.         {
19.             tmp[i++] = arr[b1] < arr[b2] ? arr[b1++] : arr[b2++];
20.         }
21.         while (b1 <= mid) tmp[i++] = arr[b1++];
22.         while (b2 <= r) tmp[i++] = arr[b2++];
23.         for (int i = l; i <= r; i++) arr[i] = tmp[i];
24.     }
25. };

复制代码

---

LCR 170. 生意业务逆序对的总数

• LCR 170. 生意业务逆序对的总数
  

   本题要求统计逆序对总数，笼统地说就是找前一部分的数有多少个数大于后一部分的数，那么对于前一部分和后一部分来说有序和乱序都是无所谓的。
  

   排升序，找cur2之前有多少个数比我大。

1. class Solution {
2.     vector<int> tmp;
3. public:
4.     int reversePairs(vector<int>& record) {
5.         int sz = record.size();
6.         tmp.resize(sz);
7.         return MergeSort(record, 0, sz - 1);
8.     }
9.     int MergeSort(vector<int>& arr, int l, int r)
10.     {
11.         if (l >= r) return 0;
12.         int mid = (l + r) >> 1;
13.         int ret = 0; // 逆序对个数
14.         ret += MergeSort(arr, l, mid);
15.         ret += MergeSort(arr, mid + 1, r);
16.         int b1 = l, b2 = mid + 1, i = l;
17.         while (b1 <= mid && b2 <= r)
18.         {
19.             // 拍升序，找b2之前有多少个数比我大
20.             if (arr[b1] <= arr[b2]) tmp[i++] = arr[b1++];
21.             else
22.             {
23.                 tmp[i++] = arr[b2++];
24.                 ret += mid - b1 + 1;
25.             }
26.         }
27.         while (b1 <= mid) tmp[i++] = arr[b1++];
28.         while (b2 <= r) tmp[i++] = arr[b2++];
29.         for (int i = l; i <= r; i++) arr[i] = tmp[i];
30.         return ret;
31.     }
32. };

复制代码

   排降序，找cur1之后有多少个数比我小。

1. class Solution {
2.     vector<int> tmp;
3. public:
4.     int reversePairs(vector<int>& record) {
5.         int sz = record.size();
6.         tmp.resize(sz);
7.         return MergeSort(record, 0, sz - 1);
8.     }
9.     int MergeSort(vector<int>& arr, int l, int r)
10.     {
11.         if (l >= r) return 0;
12.         int mid = (l + r) >> 1;
13.         int ret = 0; // 逆序对个数
14.         ret += MergeSort(arr, l, mid);
15.         ret += MergeSort(arr, mid + 1, r);
16.         int b1 = l, b2 = mid + 1, i = l;
17.         while (b1 <= mid && b2 <= r)
18.         {
19.             // 排降序，找b1之后有多少个数比我小
20.             if (arr[b1] <= arr[b2]) tmp[i++] = arr[b2++];
21.             else
22.             {
23.                 tmp[i++] = arr[b1++];
24.                 ret += r - b2 + 1;
25.             }
26.         }
27.         while (b1 <= mid) tmp[i++] = arr[b1++];
28.         while (b2 <= r) tmp[i++] = arr[b2++];
29.         for (int i = l; i <= r; i++) arr[i] = tmp[i];
30.         return ret;
31.     }
32. };

复制代码

---

盘算右侧小于当前元素的个数

• 盘算右侧小于当前元素的个数
  

1. class Solution {
2.     vector<int> ret;
3.     vector<int> index; // 绑定元素和其下标
4.     vector<int> tmp;
5.     vector<int> tmpindex;
6. public:
7.     vector<int> countSmaller(vector<int>& nums) {
8.         int n = nums.size();
9.         ret.resize(n);
10.         index.resize(n);
11.         tmp.resize(n);
12.         tmpindex.resize(n);
13.         for (int i = 0; i < n; i++) index[i] = i;
14.         MergeSort(nums, 0, n - 1);
15.         return ret;
16.     }
17.     void MergeSort(vector<int>& arr, int l, int r)
18.     {
19.         if (l >= r) return;
20.         int mid = (l + r) >> 1;
21.         MergeSort(arr, l, mid);
22.         MergeSort(arr, mid + 1, r);
23.         int b1 = l, b2 = mid + 1, i = l;
24.         while (b1 <= mid && b2 <= r)
25.         {
26.             if (arr[b1] <= arr[b2])
27.             {
28.                 tmp[i] = arr[b2];
29.                 tmpindex[i++] = index[b2++]; // 下标和元素同步移动
30.             }
31.             else
32.             {
33.                 ret[index[b1]] += r - b2 + 1;
34.                 tmp[i] = arr[b1];
35.                 tmpindex[i++] = index[b1++];
36.             }
37.         }
38.         while (b1 <= mid)
39.         {
40.             tmp[i] = arr[b1];
41.             tmpindex[i++] = index[b1++];
42.         }
43.         while (b2 <= r)
44.         {
45.             tmp[i] = arr[b2];
46.             tmpindex[i++] = index[b2++];
47.         }
48.         for (int i = l; i <= r; i++)
49.         {
50.             arr[i] = tmp[i];
51.             index[i] = tmpindex[i];
52.         }
53.     }
54. };

复制代码

---

翻转对

• 翻转对
  

1. class Solution {
2.     vector<int> tmp;
3. public:
4.     int reversePairs(vector<int>& nums) {
5.         int n = nums.size();
6.         tmp.resize(n);
7.         return MergeSort(nums, 0, n - 1);
8.     }
9.     int MergeSort(vector<int>& arr, int l, int r)
10.     {
11.         if (l >= r) return 0;
12.         int mid = (l + r) >> 1;
13.         int ret = 0; // 统计翻转对个数
14.         ret += MergeSort(arr, l, mid);
15.         ret += MergeSort(arr, mid + 1, r);
16.         int b1 = l, b2 = mid + 1, i = l;
17.         // 和归并的逻辑不同，在归并之前统计
18.         while (b1 <= mid && b2 <= r)
19.         {
20.             if (arr[b1] / 2.0 <= arr[b2]) b2++; // 做除法，防止溢出
21.             else
22.             {
23.                 ret += r - b2 + 1;
24.                 b1++;
25.             }
26.         }
27.         b1 = l, b2 = mid + 1;
28.         while (b1 <= mid && b2 <= r)
29.             tmp[i++] = arr[b1] <= arr[b2] ? arr[b2++] : arr[b1++];
30.         while (b1 <= mid) tmp[i++] = arr[b1++];
31.         while (b2 <= r) tmp[i++] = arr[b2++];
32.         for (int k = l; k <= r; k++) arr[k] = tmp[k];
33.         return ret;
34.     }
35. };

复制代码

---

本篇文章的分享就到这里了，如果您以为在本文有所劳绩，还请留下您的三连支持哦~