归并排序
912. 排序数组
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// 分治-治
void merge(vector<int> &arr, int left, int mid, int right, vector<int> &temp) {
// [left, mid]和[mid+1, right]两个有序数组
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j])
temp[index++] = arr[i++];
else
temp[index++] = arr[j++];
}
// 剩余元素直接放入temp
while (i <= mid) temp[index++] = arr[i++];
while (j <= right) temp[index++] = arr[j++];
// 放回原数组
index = 0;
while (left <= right) arr[left++] = temp[index++];
}
// 分治-分
// T(n) = 2 * T(n/2) + O(n)
// a = 2, b = 2, c = 1, 根据 master 公式,时间复杂度为 O(n * logn)
// 空间复杂度 O(n)
void divide(vector<int> &arr, int left, int right, vector<int> &temp) {
if (left >= right) return;
int mid = left + ((right - left) >> 2);
// 左边归并排序
divide(arr, left, mid, temp);
// 右边归并排序
divide(arr, mid + 1, right, temp);
// 合并两个有序序列
merge(arr, left, mid, right, temp);
}
// 递归版归并排序
void mergeSort(vector<int> &arr) {
vector<int> temp(arr.size());
divide(arr, 0, arr.size() - 1, temp);
}
vector<int> sortArray(vector<int> &nums) {
mergeSort(nums);
return nums;
}
};
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// 分治-治
void merge(vector<int> &arr, int left, int mid, int right, vector<int> &temp) {
// [left, mid]和[mid+1, right]两个有序数组
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j])
temp[index++] = arr[i++];
else
temp[index++] = arr[j++];
}
// 剩余元素直接放入temp
while (i <= mid) temp[index++] = arr[i++];
while (j <= right) temp[index++] = arr[j++];
// 放回原数组
index = 0;
while (left <= right) arr[left++] = temp[index++];
}
// 非递归版归并排序
void mergeSort(vector<int> &arr) {
vector<int> temp(arr.size());
int n = arr.size();
// 执行 O(logn) 次
for (int left, mid, right, step = 1; step < n; step <<= 1) {
left = 0;
// O(n)
while (left < n) {
mid = left + step - 1;
// 没有右侧
if (mid + 1 >= n) break;
// 求右边界
right = min(left + (step << 1) - 1, n - 1);
merge(arr, left, mid, right, temp);
// 找下一组
left = right + 1;
}
}
}
vector<int> sortArray(vector<int> &nums) {
mergeSort(nums);
return nums;
}
};
归并分治
- 思考一个问题在大范围上的答案,是否等于:左部分答案 + 右部分答案 + 跨越左右产生的答案
- 计算跨越左右产生的答案时,如果加上左右两侧都有序,能不能简化计算
计算数组的小和
#include <iostream>
#include <vector>
using namespace std;
vector<int> temp;
void merge(vector<int> &arr, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
while (i <= mid) temp[index++] = arr[i++];
while (j <= right) temp[index++] = arr[j++];
index = 0;
while (left <= right) arr[left++] = temp[index++];
}
// 返回小和,且把数组这一段变成有序
long divide(vector<int> &arr, int left, int right) {
if (left >= right) return 0;
int mid = left + ((right - left) >> 1);
// 分别计算两侧的小和
long leftSum = divide(arr, left, mid);
long rightSum = divide(arr, mid + 1, right);
// 两部分都已经有序
long midSum = 0;
for (int l = left, r = mid + 1, sum = 0; r <= right; r++) {
// 找到第一个大于 arr[r] 的位置
while (l <= mid && arr[l] <= arr[r]) {
sum += arr[l++];
}
midSum += sum;
}
merge(arr, left, mid, right);
return leftSum + midSum + rightSum;
}
int main() {
int n;
cin >> n;
vector<int> arr(n);
temp.resize(n);
for (int i = 0; i < n; ++i)
cin >> arr[i];
cout << divide(arr, 0, n - 1);
}
493. 翻转对
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> temp;
void merge(vector<int> &arr, int left, int mid, int right) {
int i = left;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
while (i <= mid) temp[index++] = arr[i++];
while (j <= right) temp[index++] = arr[j++];
index = 0;
while (left <= right) arr[left++] = temp[index++];
}
int divide(vector<int> &nums, int left, int right) {
if (left >= right) return 0;
int mid = left + ((right - left) >> 1);
int leftSum = divide(nums, left, mid);
int rightSum = divide(nums, mid + 1, right);
int midSum = 0;
for (int l = left, r = mid + 1, sum = 0; l <= mid; ++l) {
while (r <= right && ((long) nums[l] > (long) 2 * nums[r])) {
sum++;
r++;
}
midSum += sum;
}
merge(nums, left, mid, right);
return leftSum + midSum + rightSum;
}
int reversePairs(vector<int> &nums) {
temp.resize(nums.size());
return divide(nums, 0, nums.size() - 1);
}
};
没有回复内容