【算法專題】分治

分治 - 快速排序

分治 - 快速排序
- 1. 顏色分類
- 2. 排序數組(快速排序)
- 3. 數組中的第K個最大元素
- 4. 庫存管理Ⅲ
- 5. 排序數組(歸并排序)
- 6. 交易逆序對的總數
- 7. 計算右側小于當前元素的個數
- 8. 翻轉對

分治 - 快速排序

1. 顏色分類

做題鏈接 -> Leetcode -75.顏色分類

題目：給定一個包含紅色、白色和藍色、共 n 個元素的數組 nums ，原地對它們進行排序，使得相同顏色的元素相鄰，并按照紅色、白色、藍色順序排列。
我們使用整數 0、 1 和 2 分別表示紅色、白色和藍色。
必須在不使用庫內置的 sort 函數的情況下解決這個問題。

示例 1：
輸入：nums = [2, 0, 2, 1, 1, 0]
輸出：[0, 0, 1, 1, 2, 2]

示例 2：
輸入：nums = [2, 0, 1]
輸出：[0, 1, 2]

提示：
n == nums.length
1 <= n <= 300
nums[i] 為 0、1 或 2

思路：快排思想，三指針法使數組分三塊。類比數組分兩塊的算法思想，這里是將數組分成三塊，那么我們可以再添加?個指針，實現數組分三塊。

設數組大小為 n ，定義三個指針 left, cur, right :

left ：用來標記 0(紅色) 序列的末尾，因此初始化為 -1 ；
cur ：用來掃描數組，初始化為 0 ；
right ：用來標記 2(藍色) 序列的起始位置，因此初始化為 n 。

在 cur 往后掃描的過程中，保證：

[0, left] 內的元素都是 0(紅色) ；
[left + 1, cur - 1] 內的元素都是 1(白色) ；
[cur, right - 1] 內的元素是待定元素；
[right, n] 內的元素都是 2(藍色) .

代碼如下：

		class Solution {public:void sortColors(vector<int>& nums) {// 使用三指針將數組分為三塊，最終分為以下三個模塊：// [0, left] 表示 0(紅色) 序列；// [left + 1, right - 1] 表示 1(白色) 序列；// [right, numsSize - 1] 表示 2(藍色) 序列。     int cur = 0, left = -1, right = nums.size();while(cur < right){if(nums[cur] == 0) swap(nums[++left], nums[cur++]);else if(nums[cur] == 1) cur++;else swap(nums[--right], nums[cur]);}}};

2. 排序數組(快速排序)

做題鏈接 -> Leetcode -912.排序數組

題目：給你一個整數數組 nums，請你將該數組升序排列。

示例 1：
輸入：nums = [5, 2, 3, 1]
輸出：[1, 2, 3, 5]

示例 2：
輸入：nums = [5, 1, 1, 2, 0, 0]
輸出：[0, 0, 1, 1, 2, 5]

提示：
1 <= nums.length <= 5 * 10^4
5 * 10^4 <= nums[i] <= 5 * 10^4

由于思路比較明顯，使用快速選擇算法，遞歸處理選取一個基準值 key 將數組分為三塊，下面直接看代碼：

		class Solution {public:vector<int> sortArray(vector<int>& nums) {// 種下一個隨機數種子srand(time(nullptr));// 快速選擇算法，將數組劃分為三個區間my_qsort(nums, 0, nums.size() - 1);return nums;}void my_qsort(vector<int>& nums, int l, int r){if(l >= r) return;// 將數組分三塊int key = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while(i < right){if(nums[i] > key) swap(nums[i], nums[--right]);else if(nums[i] == key) ++i;else swap(nums[++left], nums[i++]);}// [l, left] [left + 1, right - 1] [right, r]my_qsort(nums, l, left);my_qsort(nums, right, r);}// 獲取數組中隨機一個數// 讓隨機數 % 上區間大小，然后加上區間的左邊界int getRandom(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}};

3. 數組中的第K個最大元素

題目鏈接 -> Leetcode -215.數組中的第K個最大元素

Leetcode -215.數組中的第K個最大元素

題目：給定整數數組 nums 和整數 k，請返回數組中第 k 個最大的元素。
請注意，你需要找的是數組排序后的第 k 個最大的元素，而不是第 k 個不同的元素。
你必須設計并實現時間復雜度為 O(n) 的算法解決此問題。

示例 1:
輸入: [3, 2, 1, 5, 6, 4] , k = 2
輸出 : 5

示例 2 :
輸入 : [3, 2, 3, 1, 2, 4, 5, 5, 6] , k = 4
輸出 : 4

提示：

1 <= k <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4

思路是使用快排思想，將數組分為三塊，然后分三種情況討論，具體思路參考代碼解析；

代碼如下：

		class Solution {public:int findKthLargest(vector<int>& nums, int k){srand(time(nullptr));return FindMaxTopk(nums, 0, nums.size() - 1, k);}int FindMaxTopk(vector<int>& nums, int l, int r, int k){if (l == r) return nums[l];// 根據 key 將數組分為三塊int key = getRandom(nums, l, r);int i = l, left = l - 1, right = r + 1;while (i < right){if (nums[i] < key) swap(nums[++left], nums[i++]);else if (nums[i] == key) i++;else swap(nums[--right], nums[i]);}// [l, left] [left + 1, right - 1] [right, r]int part2 = right - left - 1, part3 = r - right + 1;// 分情況討論// 情況1、區間3的個數大于等于k，那么目標值一定在區間3if (part3 >= k) return FindMaxTopk(nums, right, r, k);// 情況2、區間2+區間3的個數大于等于k，目標值一定在區間2，即一定是 keyelse if (part2 + part3 >= k) return key;// 情況3、如果不滿足上面情況，則目標值一定在區間1else return FindMaxTopk(nums, l, left, k - part2 - part3);}// 獲取數組內的一個隨機值int getRandom(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}};

4. 庫存管理Ⅲ

題目鏈接 -> Leetcode -LCR 159.庫存管理Ⅲ

Leetcode -LCR 159.庫存管理Ⅲ

題目：倉庫管理員以數組 stock 形式記錄商品庫存表，其中 stock[i] 表示對應商品庫存余量。
請返回庫存余量最少的 cnt 個商品余量，返回順序不限。

示例 1：
輸入：stock = [2, 5, 7, 4], cnt = 1
輸出：[2]

示例 2：
輸入：stock = [0, 2, 3, 6], cnt = 2
輸出：[0, 2] 或[2, 0]

提示：
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

思路：與上題思路類似；在快排中，當我們把數組「分成三塊」之后： [l, left] [left + 1, right - 1] [right, r] ，我們可以通過計算每一個區間內元素的「個數」，進而推斷出最小的 k 個數在哪些區間里面。那么我們可以直接去「相應的區間」繼續劃分數組即可。

代碼如下：

		class Solution {public:void my_qsort(vector<int>& arr, int l, int r, int k){if(l >= r) return;// 根據 key 值分區間int key = getRandom(arr, l, r);int i = l, left = l - 1, right = r + 1;while(i < right){if(arr[i] < key) swap(arr[++left], arr[i++]);else if(arr[i] == key) i++;else swap(arr[--right], arr[i]);}// 根據元素個數分情況討論// [l, left] [left + 1][right - 1] [right, r]int part1 = left - l + 1, part2 = right - left - 1;if(part1 >= k) my_qsort(arr, l, left, k);else if(part1 + part2 >= k) return;else my_qsort(arr, right, r, k - part1 - part2);}// 選取基準值int getRandom(vector<int>& arr, int left, int right){return arr[rand() % (right - left + 1) + left];}vector<int> inventoryManagement(vector<int>& stock, int cnt) {srand(time(nullptr));// 快速選擇算法，將數組分為三個區間，選擇基準值key，比key小的元素全扔到左邊my_qsort(stock, 0, stock.size() - 1, cnt);return vector<int>(stock.begin(), stock.begin() + cnt);}};

5. 排序數組(歸并排序)

題目鏈接 -> Leetcode -912.排序數組(歸并排序)

Leetcode -912.排序數組(歸并排序)

題目：給你一個整數數組 nums，請你將該數組升序排列。

示例 1：
輸入：nums = [5, 2, 3, 1]
輸出：[1, 2, 3, 5]

示例 2：
輸入：nums = [5, 1, 1, 2, 0, 0]
輸出：[0, 0, 1, 1, 2, 5]

提示：

1 <= nums.length <= 5 * 10^4
5 * 10^4 <= nums[i] <= 5 * 10^4

思路：歸并排序的流程充分的體現了「分而治之」的思想，大體過程分為兩步：

分：將數組一分為二為兩部分，一直分解到數組的長度為 1 ，使整個數組的排序過程被分為「左半部分排序」 + 「右半部分排序」；
治：將兩個較短的「有序數組合并成?個長的有序數組」，一直合并到最初的長度

代碼如下：

		class Solution{vector<int> tmp;public:vector<int> sortArray(vector<int>& nums){tmp.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return nums;}void mergeSort(vector<int>& nums, int left, int right){if (left >= right) return;int mid = left + (right - left) / 2;// [left, mid] [mid + 1, right]mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 合并兩個區間// vector<int> tmp(right - left + 1);  // 可以在全局定義，提高效率int i = 0, 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];}};

6. 交易逆序對的總數

題目鏈接 -> Leetcode -LCR 170.交易逆序對的總數

Leetcode -LCR 170.交易逆序對的總數

題目：在股票交易中，如果前一天的股價高于后一天的股價，則可以認為存在一個「交易逆序對」。請設計一個程序，輸入一段時間內的股票交易記錄 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)。

限制：

0 <= record.length <= 50000

思路：用歸并排序求逆序數，主要就是在歸并排序的合并過程中統計出逆序對的數量，也就是在合并兩個有序序列的過程中，能夠快速求出逆序對的數量。

1. 為什么可以利用歸并排序？

如果我們將數組從中間劃分成兩個部分，那么我們可以將逆序對產生的方式劃分成三組：

逆序對中兩個元素：全部從左數組中選擇
逆序對中兩個元素：全部從右數組中選擇
逆序對中兩個元素：一個選左數組另一個選右數組

根據排列組合的分類相加原理，三種情況下產生的逆序對的總和，正好等于總的逆序對數量。

而這個思路正好匹配歸并排序的過程：

先排序左數組；
再排序右數組；
左數組和右數組合?為一；

因此，我們可以利用歸并排序的過程，先求出左半數組中逆序對的數量，再求出右半數組中逆序對的數量，最后求出一個選擇左邊，另一個選擇右邊情況下逆序對的數量，三者相加即可。

2. 為什么要這么做？

在歸并排序合并的過程中，我們得到的是兩個有序的數組。我們是可以利用數組的有序性，快速統計出逆序對的數量，而不是將所有情況都枚舉出來。

最核心的問題，如何在合并兩個有序數組的過程中，統計出逆序對的數量？合并兩個有序序列時求逆序對的方法有兩種：

快速統計出某個數前面有多少個數比它大；
快速統計出某個數后面有多少個數比它小；

代碼如下：

		class Solution{vector<int> tmp;public: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;// [left, mid] [mid + 1, right]int mid = left + (right - left) / 2;// 先統計兩個區間各自的逆序對個數 + 排序int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);// 兩個區間每個區間選一個進行比較，因為比較時區間已經排序好，所以當cur1中出現第一次比cur2大的數時，cur1 后面的數都可以全部統計int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] > nums[cur2]) ret += mid - cur1 + 1;tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];}// 處理細節，還沒結束的指針后的數全放入tmp中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;}};

7. 計算右側小于當前元素的個數

題目鏈接 -> Leetcode -315.計算右側小于當前元素的個數

Leetcode -315.計算右側小于當前元素的個數

題目：給你一個整數數組 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]

提示：

1 <= nums.length <= 10^5
10^4 <= nums[i] <= 10^4

思路：這一道題的解法與上一題的解法是類似的，但是這一道題要求的不是求總的個數，而是要返回一個數組，記錄每一個元素的右邊有多少個元素比自己小。

但是在我們歸并排序的過程中，元素的下標是會跟著變化的，因此我們需要一個輔助數組，來將數組元素和對應的下標綁定在一起歸并，也就是再歸并元素的時候，順勢將下標也轉移到對應的位置上。

代碼如下：

		class Solution {// 將原數組的元素和下標綁定在一起，元素順序改變時，對應的下標也跟著改變vector<int> tmpElement, tmpIndex;vector<int> index;vector<int> ret;public:vector<int> countSmaller(vector<int>& nums) {ret.resize(nums.size());index.resize(nums.size());// 初始化下標for(int i = 0; i < nums.size(); i++)index[i] = i;tmpElement.resize(nums.size());tmpIndex.resize(nums.size());mergeSort(nums, 0, nums.size() - 1);return ret;}void mergeSort(vector<int>& nums, int left, int right){if(left >= right) return;int mid = left + (right - left) / 2;// [left, mid] [mid + 1, right]mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){// index[cur1] 存的是 nums[cur1] 這個元素的原始下標if(nums[cur1] > nums[cur2]) ret[index[cur1]] += right - cur2 + 1;// 同步更新下標和元素tmpIndex[i] = nums[cur1] > nums[cur2]? index[cur1] : index[cur2];tmpElement[i++] = nums[cur1] > nums[cur2]? nums[cur1++] : nums[cur2++];}while(cur1 <= mid){tmpIndex[i] = index[cur1];tmpElement[i++] = nums[cur1++];}while(cur2 <= right){tmpIndex[i] = index[cur2];tmpElement[i++] = nums[cur2++];}// 同步拷貝下標和元素for(int j = left; j <= right; j++){index[j] = tmpIndex[j - left];nums[j] = tmpElement[j - left];}}};

8. 翻轉對

題目鏈接 -> Leetcode -493.翻轉對

Leetcode -493.翻轉對

題目：給定一個數組 nums ，如果 i < j 且 nums[i] > 2 * nums[j] 我們就將(i, j) 稱作一個重要翻轉對。
你需要返回給定數組中的重要翻轉對的數量。

示例 1：
輸入: [1, 3, 2, 3, 1]
輸出 : 2

示例 2 :
輸入 : [2, 4, 3, 5, 1]
輸出 : 3

注意 :
給定數組的長度不會超過50000。
輸入數組中的所有數字都在32位整數的表示范圍內。

思路：翻轉對和逆序對的定義大同小異，逆序對是前面的數要大于后面的數。而翻轉對是前面的?個數要大于后面某個數的兩倍。因此，我們依舊可以用歸并排序的思想來解決這個問題。

大思路與求逆序對的思路一樣，就是利用歸并排序的思想，將求整個數組的翻轉對的數量，轉換成三部分：左半區間翻轉對的數量，右半區間翻轉對的數量，一左一右選擇時翻轉對的數量。重點就是在合并區間過程中，如何計算出翻轉對的數量。

例如 left = [4, 5, 6] right = [3, 4, 5] 時，如果是歸并排序的話，我們需要計算 left 數組中有多少個能與 3 組成翻轉對。但是我們要遍歷到最后?個元素 6 才能確定，時間復雜度較高。因此我們需要在歸并排序之前完成翻轉對的統計。

下面以?個示例來模仿兩個有序序列如何快速求出翻轉對的過程：假定已經有兩個已經有序的序列 left = [4, 5, 6] right = [1, 2, 3] ；用兩個指針 cur1 和 cur2 遍歷兩個數組

對于任意給定的 left[cur1] 而言，我們不斷地向右移動 cur2，直到 left[cur1] <= 2 * right[cur2]。此時對于 right 數組而言，cur2 之前的元素全部都可以與 left[cur1] 構成翻轉對。
隨后，我們再將 cur1 向右移動?個單位，此時 cur2 指針并不需要回退（因為 left 數組是升序的）依舊往右移動直到 left[cur1] <= 2 * right[cur2]。不斷重復這樣的過程，就能夠求出所有左右端點分別位于兩個子數組的翻轉對數目。

由于兩個指針最后都是不回退的的掃描到數組的結尾，因此兩個有序序列求出翻轉對的時間復雜度是 O(N).

綜上所述，我們可以利用歸并排序的過程，將求一個數組的翻轉對轉換成求左數組的翻轉對數量 + 右數組中翻轉對的數量 + 左右數組合并時翻轉對的數量。

代碼如下：

		class Solution {vector<int> tmp;public: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;// 1.根據中間元素劃分區間int mid = left + (right - left) / 2;// 2. 先計算左右區間的翻轉對// [left, mid] [mid + 1, right]int ret = 0;ret += mergeSort(nums, left, mid);ret += mergeSort(nums, mid + 1, right);// 3.先利用左右區間有序的性質計算翻轉對的數量int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid){while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) cur2++;ret += right - cur2 + 1;cur1++;}// 4.合并歸并區間cur1 = left, cur2 = mid + 1;while(cur1 <= mid && cur2 <= right)tmp[i++] = nums[cur2] > nums[cur1]? nums[cur2++] : nums[cur1++];while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];for(int j = left; j <= right; j++)nums[j] = tmp[j - left];return ret;}};