點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”

優(yōu)質(zhì)文章，第一時(shí)間送達(dá)

? 作者?|??huansky

來(lái)源 |? urlify.cn/Ina222

一、基本概念

在計(jì)算機(jī)科學(xué)中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……

任何一個(gè)可以用計(jì)算機(jī)求解的問(wèn)題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問(wèn)題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。

例如，對(duì)于 n 個(gè)元素的排序問(wèn)題，當(dāng) n=1 時(shí)，不需任何計(jì)算。n=2 時(shí)，只要作一次比較即可排好序。n=3 時(shí)只要作 3 次比較即可，…。而當(dāng) n 較大時(shí)，問(wèn)題就不那么容易處理了。要想直接解決一個(gè)規(guī)模較大的問(wèn)題，有時(shí)是相當(dāng)困難的。

二、基本思想及策略

分治法的設(shè)計(jì)思想是：將一個(gè)難以直接解決的大問(wèn)題，分割成一些規(guī)模較小的相同問(wèn)題，以便各個(gè)擊破，分而治之。

分治策略是：對(duì)于一個(gè)規(guī)模為 n 的問(wèn)題，若該問(wèn)題可以容易地解決（比如說(shuō)規(guī)模 n 較小）則直接解決，否則將其分解為 k 個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題形式相同，遞歸地解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。這種算法設(shè)計(jì)策略叫做分治法。

如果原問(wèn)題可分割成 k 個(gè)子問(wèn)題，1

由分治法產(chǎn)生的子問(wèn)題往往是原問(wèn)題的較小模式，這就為使用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使子問(wèn)題與原問(wèn)題類(lèi)型一致而其規(guī)模卻不斷縮小，最終使子問(wèn)題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過(guò)程的產(chǎn)生。分治與遞歸像一對(duì)孿生兄弟，經(jīng)常同時(shí)應(yīng)用在算法設(shè)計(jì)之中，并由此產(chǎn)生許多高效算法。

三、分治法適用的情況

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：

1. 該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決

2. 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

3. 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；

4. 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。

第一條特征是絕大多數(shù)問(wèn)題都可以滿(mǎn)足的，因?yàn)閱?wèn)題的計(jì)算復(fù)雜性一般是隨著問(wèn)題規(guī)模的增加而增加；

第二條特征是應(yīng)用分治法的前提它也是大多數(shù)問(wèn)題可以滿(mǎn)足的，此特征反映了遞歸思想的應(yīng)用；、

第三條特征是關(guān)鍵，能否利用分治法完全取決于問(wèn)題是否具有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動(dòng)態(tài)規(guī)劃法。

第四條特征涉及到分治法的效率，如果各子問(wèn)題是不獨(dú)立的則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題，此時(shí)雖然可用分治法，但一般用動(dòng)態(tài)規(guī)劃法較好。

四、可使用分治法求解的一些經(jīng)典問(wèn)題

1. 二分搜索

2. 大整數(shù)乘法

3. Strassen矩陣乘法

4. 棋盤(pán)覆蓋

5. 合并排序

6. 快速排序

7. 線性時(shí)間選擇

8. 最接近點(diǎn)對(duì)問(wèn)題

9. 循環(huán)賽日程表

10. 漢諾塔

?

五、分治法的基本步驟

分治法在每一層遞歸上都有三個(gè)步驟：

1. 分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；

2. 解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題

3. 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

它的一般的算法設(shè)計(jì)模式如下：

Divide-and-Conquer(P)

1. if?|P|≤n0

2. then?return(ADHOC(P))

3. 將P分解為較小的子問(wèn)題 P1 ,P2 ,…,Pk

4. for?i←1?to k

5. do?yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi

6. T ← MERGE(y1,y2,…,yk) △ 合并子問(wèn)題

7. return(T)

其中 |P| 表示問(wèn)題 P 的規(guī)模；n0 為一閾值，表示當(dāng)問(wèn)題 P 的規(guī)模不超過(guò) n0 時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。ADHOC(P) 是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題P。

因此，當(dāng) P 的規(guī)模不超過(guò) n0 時(shí)直接用算法 ADHOC(P) 求解。算法 MERGE(y1,y2,…,yk) 是該分治法中的合并子算法，用于將 P 的子問(wèn)題 P1 ,P2 ,…,Pk 的相應(yīng)的解 y1，y2，…，yk 合并為 P 的解。

六、依據(jù)分治法設(shè)計(jì)程序時(shí)的思維過(guò)程

實(shí)際上就是類(lèi)似于數(shù)學(xué)歸納法，找到解決本問(wèn)題的求解方程公式，然后根據(jù)方程公式設(shè)計(jì)遞歸程序。

1. 一定是先找到最小問(wèn)題規(guī)模時(shí)的求解方法

2. 然后考慮隨著問(wèn)題規(guī)模增大時(shí)的求解方法

3. 找到求解的遞歸函數(shù)式后（各種規(guī)模或因子），設(shè)計(jì)遞歸程序即可。

?

七、示例

7.1 快速排序

簡(jiǎn)述

快速排序是一種排序執(zhí)行效率很高的排序算法，它利用分治法來(lái)對(duì)待排序序列進(jìn)行分治排序，它的思想主要是通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中的一部分比關(guān)鍵字小，后面一部分比關(guān)鍵字大，然后再對(duì)這前后的兩部分分別采用這種方式進(jìn)行排序，通過(guò)遞歸的運(yùn)算最終達(dá)到整個(gè)序列有序，下面我們簡(jiǎn)單進(jìn)行闡述。

快排思路

我們從一個(gè)數(shù)組來(lái)逐步逐步說(shuō)明快速排序的方法和思路。

1. 假設(shè)我們對(duì)數(shù)組{7, 1, 3, 5, 13, 9, 3, 6, 11}進(jìn)行快速排序。

2. 首先在這個(gè)序列中找一個(gè)數(shù)作為基準(zhǔn)數(shù)，為了方便可以取第一個(gè)數(shù)。

3. 遍歷數(shù)組，將小于基準(zhǔn)數(shù)的放置于基準(zhǔn)數(shù)左邊，大于基準(zhǔn)數(shù)的放置于基準(zhǔn)數(shù)右邊。

4. 此時(shí)得到類(lèi)似于這種排序的數(shù)組{3, 1, 3, 5, 6, 7, 9, 13, 11}。

5. 在初始狀態(tài)下7是第一個(gè)位置，現(xiàn)在需要把7挪到中間的某個(gè)位置k，也即k位置是兩邊數(shù)的分界點(diǎn)。

6. 那如何做到把小于和大于基準(zhǔn)數(shù)7的值分別放置于兩邊呢，我們采用雙指針?lè)?/strong>，從數(shù)組的兩端分別進(jìn)行比對(duì)。

7. 先從最右位置往左開(kāi)始找直到找到一個(gè)小于基準(zhǔn)數(shù)的值，記錄下該值的位置（記作?i）。

8. 再?gòu)淖钭笪恢猛艺抑钡秸业揭粋€(gè)大于基準(zhǔn)數(shù)的值，記錄下該值的位置（記作?j）。

9. 如果位置i(j-1)的位置往前和(i+1)的位置往后重復(fù)上面比對(duì)基準(zhǔn)數(shù)然后交換的步驟。

10. 如果執(zhí)行到i==j，表示本次比對(duì)已經(jīng)結(jié)束，將最后i的位置的值與基準(zhǔn)數(shù)做交換，此時(shí)基準(zhǔn)數(shù)就找到了臨界點(diǎn)的位置k，位置k兩邊的數(shù)組都比當(dāng)前位置k上的基準(zhǔn)值或都更小或都更大。

11. 上一次的基準(zhǔn)值7已經(jīng)把數(shù)組分為了兩半，基準(zhǔn)值7算是已歸位（找到排序后的位置）。

12. 通過(guò)相同的排序思想，分別對(duì)7兩邊的數(shù)組進(jìn)行快速排序，左邊對(duì)[left, k-1]子數(shù)組排序，右邊則是[k+1, right]子數(shù)組排序。

13. 利用遞歸算法，對(duì)分治后的子數(shù)組進(jìn)行排序。

快速排序之所以比較快，是因?yàn)橄啾让芭菖判颍看蔚慕粨Q都是跳躍式的，每次設(shè)置一個(gè)基準(zhǔn)值，將小于基準(zhǔn)值的都交換到左邊，大于基準(zhǔn)值的都交換到右邊，這樣不會(huì)像冒泡一樣每次都只交換相鄰的兩個(gè)數(shù)，因此比較和交換的此數(shù)都變少了，速度自然更高。當(dāng)然，也有可能出現(xiàn)最壞的情況，就是仍可能相鄰的兩個(gè)數(shù)進(jìn)行交換。

快速排序基于分治思想，它的時(shí)間平均復(fù)雜度很容易計(jì)算得到為O(NlogN)。

代碼實(shí)現(xiàn)

/**
?* 快速排序
?* @param array
?*/
public?static?void?quickSort(int[] array)?{
????int?len;
????if(array?== null
????????????|| (len = array.length) == 0
????????????|| len == 1) {
????????return?;
????}
????sort(array, 0, len - 1);
}

/**
?* 快排核心算法，遞歸實(shí)現(xiàn)
?* @param array
?* @param left
?* @param right
?*/
public?static?void?sort(int[] array, int?left, int?right)?{
????if(left > right) {
????????return;
????}
????// base中存放基準(zhǔn)數(shù)
????int?base = array[left];
????int?i = left, j = right;
????while(i != j) {
????????// 順序很重要，先從右邊開(kāi)始往左找，直到找到比base值小的數(shù)
????????while(array[j] >= base && i < j) {
????????????j--;
????????}

????????// 再?gòu)淖笸疫呎遥钡秸业奖萣ase值大的數(shù)
????????while(array[i] <= base && i < j) {
????????????i++;
????????}

????????// 上面的循環(huán)結(jié)束表示找到了位置或者(i>=j)了，交換兩個(gè)數(shù)在數(shù)組中的位置
????????if(i < j) {
????????????int?tmp = array[i];
????????????array[i] = array[j];
????????????array[j] = tmp;
????????}
????}

????// 將基準(zhǔn)數(shù)放到中間的位置（基準(zhǔn)數(shù)歸位）
????array[left] = array[i];
????array[i] = base;

????// 遞歸，繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作
????// i的索引處為上面已確定好的基準(zhǔn)值的位置，無(wú)需再處理
????sort(array, left, i - 1);
????sort(array, i + 1, right);
}

?7.2?215. 數(shù)組中的第K個(gè)最大元素

在未排序的數(shù)組中找到第 k 個(gè)最大的元素。請(qǐng)注意，你需要找的是數(shù)組排序后的第 k 個(gè)最大的元素，而不是第 k 個(gè)不同的元素。

示例 1:

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

示例 2:

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

說(shuō)明:

你可以假設(shè) k 總是有效的，且 1 ≤ k ≤ 數(shù)組的長(zhǎng)度。

思路和算法

我們可以用快速排序來(lái)解決這個(gè)問(wèn)題，先對(duì)原數(shù)組排序，再返回倒數(shù)第 kk 個(gè)位置，這樣平均時(shí)間復(fù)雜度是 O(n \log n)O(nlogn)，但其實(shí)我們可以做的更快。

在分解的過(guò)程當(dāng)中，我們會(huì)對(duì)子數(shù)組進(jìn)行劃分，如果劃分得到的 q 正好就是我們需要的下標(biāo)，就直接返回 a[q]；否則，如果 q 比目標(biāo)下標(biāo)小，就遞歸右子區(qū)間，否則遞歸左子區(qū)間。這樣就可以把原來(lái)遞歸兩個(gè)區(qū)間變成只遞歸一個(gè)區(qū)間，提高了時(shí)間效率。這就是「快速選擇」算法。

我們知道快速排序的性能和「劃分」出的子數(shù)組的長(zhǎng)度密切相關(guān)。直觀地理解如果每次規(guī)模為 n 的問(wèn)題我們都劃分成 1 和 n - 1，每次遞歸的時(shí)候又向 n?1 的集合中遞歸，這種情況是最壞的，時(shí)間代價(jià)是O(n ^ 2)O(n2)。

我們可以引入隨機(jī)化來(lái)加速這個(gè)過(guò)程，它的時(shí)間代價(jià)的期望是 O(n)，證明過(guò)程可以參考「《算法導(dǎo)論》9.2：期望為線性的選擇算法」。

class?Solution?{

????public?int?findKthLargest(int[] nums, int?k)?{
????????int?len = nums.length;
????????int?targetIndex = len - k;
????????int?low = 0, high = len - 1;
????????while?(true) {
????????????int?i = partition(nums, low, high);
????????????if?(i == targetIndex) {
????????????????return?nums[i];
????????????} else?if?(i < targetIndex) {
????????????????low = i + 1;
????????????} else?{
????????????????high = i - 1;
????????????}
????????}
????}

????/**
?????* 分區(qū)函數(shù)，將 arr[high] 作為 pivot 分區(qū)點(diǎn)
?????* i、j 兩個(gè)指針，i 作為標(biāo)記“已處理區(qū)間”和“未處理區(qū)間”的分界點(diǎn)，也即 i 左邊的（low~i-1）都是“已處理區(qū)”。
?????* j 指針遍歷數(shù)組，當(dāng) arr[j] 小于 pivot 時(shí)，就把 arr[j] 放到“已處理區(qū)間”的尾部，也即是 arr[i] 所在位置
?????* 因此 swap(arr, i, j) 然后 i 指針后移，i++
?????* 直到 j 遍歷到數(shù)組末尾 arr[high]，將 arr[i] 和 arr[high]（pivot點(diǎn)） 進(jìn)行交換，返回下標(biāo) i，就是分區(qū)點(diǎn)的下標(biāo)。
?????*/
????private?int?partition(int[] arr, int?low, int?high)?{
????????int?i = low;
????????int?pivot = arr[high];
????????for?(int?j = low; j < high; j++) {
????????????if?(arr[j] < pivot) {
????????????????swap(arr, i, j);
????????????????i++;
????????????}
????????}
????????swap(arr, i, high);
????????return?i;
????}

????private?void?swap(int[] arr, int?i, int?j)?{
????????int?tmp = arr[i];
????????arr[i] = arr[j];
????????arr[j] = tmp;
????}
}

其實(shí)這段代碼和快排很像，但是兩者得目的是不一樣的。

7.3?973. 最接近原點(diǎn)的 K 個(gè)點(diǎn)

我們有一個(gè)由平面上的點(diǎn)組成的列表 points。需要從中找出 K 個(gè)距離原點(diǎn) (0, 0) 最近的點(diǎn)。（這里，平面上兩點(diǎn)之間的距離是歐幾里德距離。）

你可以按任何順序返回答案。除了點(diǎn)坐標(biāo)的順序之外，答案確保是唯一的。?

示例 1：

輸入：points = [[1,3],[-2,2]], K = 1
輸出：[[-2,2]]
解釋?zhuān)?br mpa-from-tpl="t">(1, 3) 和原點(diǎn)之間的距離為 sqrt(10)，
(-2, 2) 和原點(diǎn)之間的距離為 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 離原點(diǎn)更近。
我們只需要距離原點(diǎn)最近的 K = 1?個(gè)點(diǎn)，所以答案就是 [[-2,2]]。

示例 2：

輸入：points = [[3,3],[5,-1],[-2,4]], K = 2
輸出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也會(huì)被接受。）

思路

我們想要一個(gè)復(fù)雜度比 N logN 更低的算法。顯然，做到這件事情的唯一辦法就是利用題目中可以按照任何順序返回 K 個(gè)點(diǎn)的條件，否則的話(huà)，必要的排序?qū)?huì)話(huà)費(fèi)我們 N logN 的時(shí)間。

我們隨機(jī)地選擇一個(gè)元素 x = A[i] 然后將數(shù)組分為兩部分：一部分是到原點(diǎn)距離小于 x 的，另一部分是到原點(diǎn)距離大于等于 x 的。這個(gè)快速選擇的過(guò)程與快速排序中選擇一個(gè)關(guān)鍵元素將數(shù)組分為兩部分的過(guò)程類(lèi)似。

如果我們快速選擇一些關(guān)鍵元素，那么每次就可以將問(wèn)題規(guī)模縮減為原來(lái)的一半，平均下來(lái)時(shí)間復(fù)雜度就是線性的。

算法

我們定義一個(gè)函數(shù) work(i, j, K)，它的功能是部分排序 (points[i], points[i+1], ..., points[j]) 使得最小的 K 個(gè)元素出現(xiàn)在數(shù)組的首部，也就是 (i, i+1, ..., i+K-1)。

首先，我們從數(shù)組中選擇一個(gè)隨機(jī)的元素作為關(guān)鍵元素，然后使用這個(gè)元素將數(shù)組分為上述的兩部分。為了能使用線性時(shí)間的完成這件事，我們需要兩個(gè)指針 i 與 j，然后將它們移動(dòng)到放錯(cuò)了位置元素的地方，然后交換這些元素。

然后，我們就有了兩個(gè)部分 [oi, i] 與 [i+1, oj]，其中 (oi, oj) 是原來(lái)調(diào)用 work(i, j, K) 時(shí)候 (i, j) 的值。假設(shè)第一部分有 10 個(gè)元，第二部分有15 個(gè)元素。如果 K = 5 的話(huà)，我們只需要對(duì)第一部分調(diào)用 work(oi, i, 5)。否則的話(huà)，假如說(shuō) K = 17，那么第一部分的 10 個(gè)元素應(yīng)該都需要被選擇，我們只需要對(duì)第二部分調(diào)用 work(i+1, oj, 7) 就行了。

class?Solution?{
????int[][] points;
????public?int[][] kClosest(int[][] points, int?K) {
????????this.points = points;
????????work(0, points.length - 1, K);
????????return?Arrays.copyOfRange(points, 0, K);
????}

????public?void?work(int?i, int?j, int?K)?{
????????if?(i >= j) return;
????????int?oi = i, oj = j;
????????int?pivot = dist(ThreadLocalRandom.current().nextInt(i, j));

????????while?(i < j) {
????????????while?(i < j && dist(i) < pivot) i++;
????????????while?(i < j && dist(j) > pivot) j--;
????????????swap(i, j);
????????}

????????if?(K <= i - oi + 1)
????????????work(oi, i, K);
????????else
????????????work(i+1, oj, K - (i - oi + 1));
????}

????public?int?dist(int?i)?{
????????return?points[i][0] * points[i][0] + points[i][1] * points[i][1];
????}

????public?void?swap(int?i, int?j)?{
????????int?t0 = points[i][0], t1 = points[i][1];
????????points[i][0] = points[j][0];
????????points[i][1] = points[j][1];
????????points[j][0] = t0;
????????points[j][1] = t1;
????}
}

可以發(fā)現(xiàn)的是，這道題目跟前面的還是很像的。

粉絲福利：108本java從入門(mén)到大神精選電子書(shū)領(lǐng)取

???

?長(zhǎng)按上方二維碼?2 秒
回復(fù)「1234」即可獲取資料以及
可以進(jìn)入java1234官方微信群

感謝點(diǎn)贊支持下哈?