《排序數組》

題目描述：

給你一個整數數組 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倍為標準然后向右移動還是統計數據，而且經過排序后，數據也會亂了，因此我們必須在排序之前就通過雙指針做好統計。