排序数组
class Solution {
vector<int> tmp;
public:
vector<int> sortArray(vector<int>& nums) {
int sz = nums.size();
tmp.resize(sz);
MergeSort(nums, 0, sz - 1);
return nums;
}
void MergeSort(vector<int>& arr, int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
MergeSort(arr, l, mid);
MergeSort(arr, mid + 1, r);
int b1 = l, b2 = mid + 1, i = l;
while (b1 <= mid && b2 <= r)
{
tmp[i++] = arr[b1] < arr[b2] ? arr[b1++] : arr[b2++];
}
while (b1 <= mid) tmp[i++] = arr[b1++];
while (b2 <= r) tmp[i++] = arr[b2++];
for (int i = l; i <= r; i++) arr[i] = tmp[i];
}
};
LCR 170. 交易逆序对的总数
本题要求统计逆序对总数，笼统地说就是找前一部分的数有多少个数大于后一部分的数，那么对于前一部分和后一部分来说有序和乱序都是无所谓的。
排升序，找cur2之前有多少个数比我大。
class Solution {
vector<int> tmp;
public:
int reversePairs(vector<int>& record) {
int sz = record.size();
tmp.resize(sz);
return MergeSort(record, 0, sz - 1);
}
int MergeSort(vector<int>& arr, int l, int r)
{
if (l >= r) return 0;
int mid = (l + r) >> 1;
int ret = 0; // 逆序对个数
ret += MergeSort(arr, l, mid);
ret += MergeSort(arr, mid + 1, r);
int b1 = l, b2 = mid + 1, i = l;
while (b1 <= mid && b2 <= r)
{
// 拍升序，找b2之前有多少个数比我大
if (arr[b1] <= arr[b2]) tmp[i++] = arr[b1++];
else
{
tmp[i++] = arr[b2++];
ret += mid - b1 + 1;
}
}
while (b1 <= mid) tmp[i++] = arr[b1++];
while (b2 <= r) tmp[i++] = arr[b2++];
for (int i = l; i <= r; i++) arr[i] = tmp[i];
return ret;
}
};
排降序，找cur1之后有多少个数比我小。
class Solution {
vector<int> tmp;
public:
int reversePairs(vector<int>& record) {
int sz = record.size();
tmp.resize(sz);
return MergeSort(record, 0, sz - 1);
}
int MergeSort(vector<int>& arr, int l, int r)
{
if (l >= r) return 0;
int mid = (l + r) >> 1;
int ret = 0; // 逆序对个数
ret += MergeSort(arr, l, mid);
ret += MergeSort(arr, mid + 1, r);
int b1 = l, b2 = mid + 1, i = l;
while (b1 <= mid && b2 <= r)
{
// 排降序，找b1之后有多少个数比我小
if (arr[b1] <= arr[b2]) tmp[i++] = arr[b2++];
else
{
tmp[i++] = arr[b1++];
ret += r - b2 + 1;
}
}
while (b1 <= mid) tmp[i++] = arr[b1++];
while (b2 <= r) tmp[i++] = arr[b2++];
for (int i = l; i <= r; i++) arr[i] = tmp[i];
return ret;
}
};
计算右侧小于当前元素的个数
class Solution {
vector<int> ret;
vector<int> index; // 绑定元素和其下标
vector<int> tmp;
vector<int> tmpindex;
public:
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
ret.resize(n);
index.resize(n);
tmp.resize(n);
tmpindex.resize(n);
for (int i = 0; i < n; i++) index[i] = i;
MergeSort(nums, 0, n - 1);
return ret;
}
void MergeSort(vector<int>& arr, int l, int r)
{
if (l >= r) return;
int mid = (l + r) >> 1;
MergeSort(arr, l, mid);
MergeSort(arr, mid + 1, r);
int b1 = l, b2 = mid + 1, i = l;
while (b1 <= mid && b2 <= r)
{
if (arr[b1] <= arr[b2])
{
tmp[i] = arr[b2];
tmpindex[i++] = index[b2++]; // 下标和元素同步移动
}
else
{
ret[index[b1]] += r - b2 + 1;
tmp[i] = arr[b1];
tmpindex[i++] = index[b1++];
}
}
while (b1 <= mid)
{
tmp[i] = arr[b1];
tmpindex[i++] = index[b1++];
}
while (b2 <= r)
{
tmp[i] = arr[b2];
tmpindex[i++] = index[b2++];
}
for (int i = l; i <= r; i++)
{
arr[i] = tmp[i];
index[i] = tmpindex[i];
}
}
};
翻转对
class Solution {
vector<int> tmp;
public:
int reversePairs(vector<int>& nums) {
int n = nums.size();
tmp.resize(n);
return MergeSort(nums, 0, n - 1);
}
int MergeSort(vector<int>& arr, int l, int r)
{
if (l >= r) return 0;
int mid = (l + r) >> 1;
int ret = 0; // 统计翻转对个数
ret += MergeSort(arr, l, mid);
ret += MergeSort(arr, mid + 1, r);
int b1 = l, b2 = mid + 1, i = l;
// 和归并的逻辑不同，在归并之前统计
while (b1 <= mid && b2 <= r)
{
if (arr[b1] / 2.0 <= arr[b2]) b2++; // 做除法，防止溢出
else
{
ret += r - b2 + 1;
b1++;
}
}
b1 = l, b2 = mid + 1;
while (b1 <= mid && b2 <= r)
tmp[i++] = arr[b1] <= arr[b2] ? arr[b2++] : arr[b1++];
while (b1 <= mid) tmp[i++] = arr[b1++];
while (b2 <= r) tmp[i++] = arr[b2++];
for (int k = l; k <= r; k++) arr[k] = tmp[k];
return ret;
}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
