目录
912. 排序数组
一、归并排序
归并排序的过程可以在逻辑上抽象成一棵二叉树，树上的每个节点的值是?nums[lo..hi]，叶子节点的值就是数组中的单个元素，排序过程如下图所示（来源：labuladong）。
merge?操作会在二叉树的每个节点上都执行一遍，执行顺序是二叉树后序遍历的顺序。?
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
temp.resize(nums.size());
Sort(nums, 0, nums.size() - 1);
return nums;
}
private:
// 初始化一个辅助数组，避免递归时内存频繁分配释放
vector<int> temp;
void Sort(vector<int>& nums, int left, int right) {
// 只剩下一个元素，无需继续排序
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
// 排序左侧数组[left, mid]
Sort(nums, left, mid);
// 排序右侧数组[mid + 1, right]
Sort(nums, mid + 1, right);
// 将有序的左右数组按顺序合并
Merge(nums, left, mid, right);
}
void Merge(vector<int>& nums, int left, int mid, int right) {
// 把 nums[left, right] 复制到辅助数组中，以便合并后的结果能够直接存入 nums
for (size_t i = left; i <= right; ++i) temp[i] = nums[i];
// 利用双指针技巧，合并两个有序数组
int left_p = left, right_p = mid + 1;
for (size_t p = left; p <= right; ++p) {
// 左侧数组已经merge完毕，只需要移动右侧数组的指针
if (left_p == mid + 1) nums[p] = temp[right_p++];
// 右侧数组已经merge完毕，只需要移动左侧数组的指针
else if (right_p == right + 1) nums[p] = temp[left_p++];
// 升序：左侧数比右侧数小，加入左侧元素
else if (temp[left_p] < temp[right_p]) nums[p] = temp[left_p++];
// 升序：右侧数比左侧数小，加入右侧元素
else nums[p] = temp[right_p++];
}
}
};归并排序的技巧在于：不是在?merge?函数执行的时候 new 辅助数组，而是提前把?temp?辅助数组 new 出来了，这样就避免了在递归中频繁分配和释放内存可能产生的性能问题。
?时间复杂度：O(NlogN)
对于归并排序来说，时间复杂度集中在?
merge?函数遍历?nums[left,right]?的过程。Merge执行的次数是二叉树节点的个数，每次执行的复杂度就是每个节点代表的子数组的长度，所以总的时间复杂度就是整棵树中「数组元素」的个数。从整体上看，二叉树的高度是?
logN，其中每一层的元素个数就是原数组的长度?N，所以总的时间复杂度就是?O(NlogN)。【logN层，每层N次】
?315. 计算右侧小于当前元素的个数[*]
class Solution {
typedef pair<int, int> Vidx;
public:
vector<int> countSmaller(vector<int>& nums) {
// 初始化数组，使之成为键值对，携带下标信息
vector<Vidx> arr;
for (int i = 0; i < nums.size(); ++i) {
arr.push_back(make_pair(nums[i], i));
}
temp.resize(nums.size());
count.resize(nums.size());
Sort(arr, 0, arr.size() - 1);
return count;
}
private:
// 记录右侧小于 nums[i] 的元素的数量
vector<int> count;
// 初始化一个辅助数组，避免递归时内存频繁分配释放；同时还要记录下标位置
vector<Vidx> temp;
void Sort(vector<Vidx>& arr, int left, int right) {
// 只剩下一个元素，无需继续排序
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
// 排序左侧数组[left, mid]
Sort(arr, left, mid);
// 排序右侧数组[mid + 1, right]
Sort(arr, mid + 1, right);
// 将有序的左右数组按顺序合并
Merge(arr, left, mid, right);
}
void Merge(vector<Vidx>& arr, int left, int mid, int right) {
// 把 nums[left, right] 复制到辅助数组中，以便合并后的结果能够直接存入 nums
for (size_t i = left; i <= right; ++i) temp[i] = arr[i];
// 利用双指针技巧，合并两个有序数组
int left_p = left, right_p = mid + 1;
for (size_t p = left; p <= right; ++p) {
// 左侧数组已经merge完毕，只需要移动右侧数组的指针
if (left_p == mid + 1) arr[p] = temp[right_p++];
// 右侧数组已经merge完毕，只需要移动左侧数组的指针
else if (right_p == right + 1) {
arr[p] = temp[left_p++];
// 更新 count 数组
count[arr[p].second] += right_p - mid - 1;
}
// 升序：左侧数比右侧数小，加入左侧元素
else if (temp[left_p].first <= temp[right_p].first) {
arr[p] = temp[left_p++];
// 更新 count 数组
count[arr[p].second] += right_p - mid - 1;
}
// 升序：右侧数比右侧数小，加入右侧元素
else arr[p] = temp[right_p++];
}
}
};在使用?merge?函数合并两个有序数组的时候，其实是可以知道一个元素?nums[i]?后边有多少个元素比?nums[i]?小的。如下图所示（来源：labuladong）:
把?temp[i]?放到?nums[p]?上时，我们不仅知道?temp[i] < temp[j]，还能确定?左闭右开区间?[mid + 1, j)?中的元素都是?temp[i]?右侧的、较小的元素。
换句话说，在对?
nuns[lo..hi]?合并的过程中，每当执行?nums[p] = temp[i]?时，就可以确定?temp[i]?这个元素后面比它小的元素个数为?j - mid - 1。
?count应当不断被累加，因为每次递归时，累加的都是新的右侧的数组中比nums[p]小的元素数量。
493. 翻转对
class Solution {
public:
int reversePairs(vector<int>& nums) {
res = 0;
temp.resize(nums.size());
Sort(nums, 0, nums.size() - 1);
return res;
}
private:
int res;
// 初始化一个辅助数组，避免递归时内存频繁分配释放
vector<int> temp;
void Sort(vector<int>& nums, int left, int right) {
// 只剩下一个元素，无需继续排序
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
// 排序左侧数组[left, mid]
Sort(nums, left, mid);
// 排序右侧数组[mid + 1, right]
Sort(nums, mid + 1, right);
// 将有序的左右数组按顺序合并
Merge(nums, left, mid, right);
}
void Merge(vector<int>& nums, int left, int mid, int right) {
// 把 nums[left, right] 复制到辅助数组中，以便合并后的结果能够直接存入 nums
for (size_t i = left; i <= right; ++i) temp[i] = nums[i];
// 对两个有序数组，判断左侧元素nums[i] > 2*nums[j]是否成立
// 由于数组有序，可以优化统计效率:维护左闭右开区间 [mid+1, end) 中的元素乘 2 小于 nums[i]
int end = mid + 1;
for (size_t i = left; i <= mid; ++i) {
while (end <= right && (long)nums[i] > 2 * (long)nums[end]) end++;
res += end - mid - 1;
}
// 利用双指针技巧，合并两个有序数组
int left_p = left, right_p = mid + 1;
for (size_t p = left; p <= right; ++p) {
// 左侧数组已经merge完毕，只需要移动右侧数组的指针
if (left_p == mid + 1) nums[p] = temp[right_p++];
// 右侧数组已经merge完毕，只需要移动左侧数组的指针
else if (right_p == right + 1) nums[p] = temp[left_p++];
// 升序：右侧数比左侧数小，加入右侧元素
else if (temp[left_p] > temp[right_p]) nums[p] = temp[right_p++];
// 升序：左侧数比右侧数小，加入左侧元素
else nums[p] = temp[left_p++];
}
}
};本题所在Merge函数中添加了一段代码，在两个有序数组内，寻找右侧数组小于左侧数组当前元素的一半的元素数量。
【这种i<j，或寻找右侧/左侧元素个数的问题，都可以用分治思想解决，都可以借助于归并排序的模板】
327. 区间和的个数[*]
class Solution {
public:
int countRangeSum(vector<int>& nums, int lower, int upper) {
res = 0;
this->lower = lower;
this->upper = upper;
temp.resize(nums.size() + 1, 0);
preSum.resize(nums.size() + 1, 0);
for (size_t i = 0; i < nums.size(); ++i) preSum[i + 1] = preSum[i] + nums[i];
Sort(preSum, 0, preSum.size() - 1);
return res;
}
private:
int res;
int lower;
int upper;
// 前缀和数组，用于快速计算区间和。用long类型防止和溢出
vector<long> preSum;
// 初始化一个辅助数组，避免递归时内存频繁分配释放
vector<long> temp;
void Sort(vector<long>& nums, int left, int right) {
// 只剩下一个元素，无需继续排序
if (left == right) {
return;
}
int mid = left + (right - left) / 2;
// 排序左侧数组[left, mid]
Sort(nums, left, mid);
// 排序右侧数组[mid + 1, right]
Sort(nums, mid + 1, right);
// 将有序的左右数组按顺序合并
Merge(nums, left, mid, right);
}
void Merge(vector<long>& nums, int left, int mid, int right) {
// 把 nums[left, right] 复制到辅助数组中，以便合并后的结果能够直接存入 nums
for (size_t i = left; i <= right; ++i) temp[i] = nums[i];
// 维护左闭右开区间 [start, end) 中的元素和 nums[i] 的差在 [lower, upper] 中
int start = mid + 1;
int end = mid + 1;
for (size_t i = left; i <= mid; ++i) {
// 如果 nums[i] 对应的区间是 [start, end)，
// 那么 nums[i+1] 对应的区间一定会整体右移，类似滑动窗口
while (start <= right && nums[start] - nums[i] < lower) start++;
while (end <= right && nums[end] - nums[i] <= upper) end++;
res += end - start;
}
// 利用双指针技巧，合并两个有序数组
int left_p = left, right_p = mid + 1;
for (size_t p = left; p <= right; ++p) {
// 左侧数组已经merge完毕，只需要移动右侧数组的指针
if (left_p == mid + 1) nums[p] = temp[right_p++];
// 右侧数组已经merge完毕，只需要移动左侧数组的指针
else if (right_p == right + 1) nums[p] = temp[left_p++];
// 升序：右侧数比左侧数小，加入右侧元素
else if (temp[left_p] > temp[right_p]) nums[p] = temp[right_p++];
// 升序：左侧数比右侧数小，加入左侧元素
else nums[p] = temp[left_p++];
}
}
};首先，看到区间和时，要想到利用前缀和数组进行快速计算。于是就可以对前缀和数组进行归并排序，在merge函数中统计区间和满足要求的个数。
由于merge时两个数组是有序的，可以进行效率优化，即维护一个滑动窗口，让窗口中的元素和?nums[i]?的差落在?[lower, upper]?中。
归并排序算法，递归的?
sort?函数就是二叉树的遍历函数，而?merge?函数就是在每个节点上做的事情。在每个节点上做事时都可以满足以下两点：操作两个有序数组、左侧的元素在原数组中的下标一定小于右侧的元素。尤其是第二点，对于上述“右侧元素小于当前元素数目”、“翻转对”和“区间和（利用前缀和计算时要求j>i）”等问题适用。
?