算法分析—— 《归并排序》

《排序数组》

题目描述：

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

代码实现：

class Solution 
{
public:vector<int> tmp;vector<int> sortArray(vector<int>& nums) {tmp.resize(nums.size());MergeSort(nums, 0, nums.size() - 1);return nums;}void MergeSort(vector<int>& nums, int l, int r){if(l >= r) return;int mid = (r + l) >> 1;MergeSort(nums, l, mid);MergeSort(nums, mid + 1, r);int cur1 = l, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= r) tmp[i++] = nums[cur1] >= nums[cur2] ? nums[cur2++] : nums[cur1++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= r) tmp[i++] = nums[cur2++];for(int i = l; i <= r; ++i) nums[i] = tmp[i - l];}
};

代码解析：

对于同一种排序题目来说，不仅仅要去掌握快速排序，接触其他的排序新思路也尤为重要，不管是归并排序还是快速排序，其本质的思路就是两个字 —— 分治。

所以归并排序是最简单的，利用递归的思路，我们就认为这个递归操作一定可以做到，那么最终就是实现一个「合并两个有序数组」的操作。

那这个操作很简单，利用双指针就可以非常轻松的实现了，在这里我就不过多赘述，因为确实不难。

《交易逆序对的总数》

题目描述：

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1：

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

代码实现：

class Solution 
{
public:vector<int> tmp;int reversePairs(vector<int>& record) {tmp.resize(record.size());return mergesort(record, 0, record.size() - 1);}int mergesort(vector<int>& record, int left, int right){if(left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += mergesort(record, left, mid);ret += mergesort(record, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){if(record[cur1] <= record[cur2]) tmp[i++] = record[cur1++];else {ret += (mid - cur1 + 1);tmp[i++] = record[cur2++];} }while(cur1 <= mid) tmp[i++] = record[cur1++];while(cur2 <= right) tmp[i++] = record[cur2++];for(int i = left; i <= right; ++i){record[i] = tmp[i - left];}return ret;}};

代码解析：

题目意思很好理解，就是定一个数字，然后去后面找有没有比这个数小的，记住一定是要去后面找。

最简单的解法就是利用双指针套两层for循环直接暴力解决，但是最终会超时，这就很尴尬。

第二个方法，就是利用分治归并的思路来解决题目。

我们最主要的研究可以转换成「找出该数前，有多少个数比我大」

那现在假设我们利用了「归并」将数组排好了升序了，但是还没有「合并两个有序数组」，大致的情况如下：

因为这个判断也需要指针移动，所以我们就可以在排序的过程中，就将答案给算出来。

因为单调性，所以在nums[cur1] > nums[cur2]的情况下，cur1后面的数都大于nums[cur2]

《计算右侧小于当前元素的个数》

题目描述：

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

代码实现：

class Solution 
{
public:vector<pair<int, int>> tmp;     // 追踪numsvector<int> ret;                // 接受答案vector<pair<int, int>> assist;  // 哈希绑定(原数据 + 下标)vector<int> countSmaller(vector<int> &nums){for (int i = 0; i < nums.size(); ++i){assist.push_back(make_pair(nums[i], i));}ret.resize(nums.size());tmp.resize(assist.size());Mergesort(assist, 0, nums.size() - 1);return ret;}void Mergesort(vector<pair<int, int>> &assist, int left, int right){if (left >= right) return;int mid = (right + left) >> 1;Mergesort(assist, left, mid);Mergesort(assist, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (assist[cur1].first <= assist[cur2].first) tmp[i++] = assist[cur2++];else{ret[assist[cur1].second] += right - cur2 + 1;tmp[i++] = assist[cur1++];}}while (cur1 <= mid) tmp[i++] = assist[cur1++];while (cur2 <= right) tmp[i++] = assist[cur2++];for (int i = left; i <= right; ++i) assist[i] = tmp[i - left];}};

代码解析：

这道题目总体来说，与上一道题的算法思路一样，上一道题是记录有多少个前面大于后面的数字，而这道题是将每个坐标的数字统计起来，然后将确切的数据按照下标统计。

所以使用归并排序，我们无法固定住下标，因为下标会随着排序而发生变化。所以这正是我们需要去解决的。

一开始我考虑使用哈希表，但是数组可能会出现重复数据，所以哈希表pass了，但是我们可以仍然采用哈希的算法思路，将数据和下标绑定在一起。那么这时候我们可以使用vector<pair<int, int>>来模拟哈希表。

拿题目自带的例子：

这样子在排序改变数据位置的同时，下标也随之改变了。

然后也是基于上一道题了，不过这里我们不应该排「升序」，而是排「降序」，因为我们是要找右侧有多少个元素比自己小，那竟然如此我们可以画个图理解理解。

因为单调性，所以nums[cur1]大于cur2后面的全部数。

剩下的思路也是一样的，只是需要注意pair的first和seconde的取值。

《翻转对》

题目描述：

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对****。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

代码实现：

class Solution 
{
public:vector<int> tmp;int reversePairs(vector<int>& nums) {tmp.resize(nums.size());return MergeSort(nums, 0, nums.size() - 1);}int MergeSort(vector<int>& nums, int left, int right){if(left >= right) return 0;int mid = (left + right) >> 1;int ret = 0;ret += MergeSort(nums, left, mid);ret += MergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid){while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) ++cur2;if(cur2 > right) break;ret += (right - cur2 + 1);++cur1;}cur1 = left, cur2 = mid + 1;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];return ret;}};

代码解析：

一样，这道题和前面的内容算法一样，只不过这里是判断是否大于2倍。

那在这里我们在实现「合并两个有序数组」之前，就可以先通过双指针进行一次判断，再去排序，因为你无法控制是以2倍为标准然后向右移动还是统计数据，而且经过排序后，数据也会乱了，因此我们必须在排序之前就通过双指针做好统计。