如何使用分治算法的思想，分治技巧详解

技术分享 3年前 (2022-11-18) 0 999+

关注

分治算法

分治算法

分治算法的思想

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治算法和递归的区别

分治是处理问题的思想，递归是一种编程技巧。分治一般都比较适合用用递归来实现。

分治算法的实现中，每一层地递归都会涉及到下面三个操作：

分解：将原问题分解成一系列子问题；

解决：将子问题的结果合并成原问题。

使用分治算法需要满足的条件

1、原问题与分解成的小问题具有相同的模式；

2、原问题分解成的子问题可以独立求解，子问题之间没有相关性；

3、具有分解终止条件，也就是说，当问题足够小时，可以直接求解；

4、可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

经典题目

1、二分搜索

给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4

示例2:

输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums 中因此返回 -1

题目链接：https://leetcode.cn/problems/binary-search

解题思路

1、满足分支算法的思想，将为题分解为规模较小的相同问题时，就比较容易求解；

2、找出中间的值和目标值进行比较，通过判断大小，来不断的缩小问题的求解范围；

3、这样每次的求解，总是能将问题的范围缩小一半，或者找出目标值。

时间复杂度：O(logn)

空间复杂度：O(1)

func search(nums []int, target int) int { 	left, right := 0, len(nums)-1 	for left <= right { 		mid := (right + left) / 2 		if nums[mid] == target { 			return mid 		} else if nums[mid] > target { 			right = mid - 1 		} else if nums[mid] < target { 			left = mid + 1 		} 	}  	return -1 }

2、第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用bool isBadVersion(version)接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5)-> true 调用 isBadVersion(4)-> true 所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1 输出：1

链接：https://leetcode.cn/problems/first-bad-version

题解：

这道题目是二分查找的变种题目，找出最近的一个出错的版本，也就是出错版本的左边都是出错的版本；

所以利用二分查找，找出出错的又边界即可

/**  * Forward declaration of isBadVersion API.  * @param   version   your guess about first bad version  * @return 	 	      true if current version is bad  *			          false if current version is good  * func isBadVersion(version int) bool;  */  func firstBadVersion(n int) int { 	left, right := 0, n 	for left < right { 		mid := (right + left) / 2 		if isBadVersion(mid) { 			right = mid 		} else { 			left = mid + 1 		} 	}  	return right }  // 测试函数 func isBadVersion(n int) bool { 	return false }

3、快速排序

快速排序在我们刚学习算法的时候就遇到了过了，其中它使用到的算法思想就是分治策略。

它的处理思路就是，会选中一个基准数，通过一趟排序，和当前的基准数进行比较，将数据分总成两部分，一部分大于基准数，另一部分小于基准数。

然后对这两部分数据在进行上面的操作，直到所有的数据都有序，整个排序的过程可以使用递归去实现。

快排的时间复杂度：平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n2

空间复杂度：最好空间复杂度为 O(logn)，最坏空间复杂度为 O(n)

上代码

func QuickSort(arr []int) { 	quickSort(arr, 0, len(arr)-1) }  func quickSort(data []int, l, u int) { 	if l < u { 		m := partition(data, l, u) 		quickSort(data, l, m-1) 		quickSort(data, m, u) 	} }  func partition(data []int, l, u int) int { 	quick := data[l] 	left := l  	for i := l + 1; i <= u; i++ { 		if data[i] <= quick { 			left++ 			data[left], data[i] = data[i], data[left] 		} 	} 	data[l], data[left] = data[left], data[l] 	return left + 1 }

4、归并排序

归并排序也是使用分治思想实现的一个比较经典的栗子，这里来分析下

归并排序的处理思路：

1、首先拆分子序列，使得子序列很容易排序，然后对子序列进行排序；

2、然后是合并的过程，将有序的子序列合并；

3、合并子序列的过程；

1、申请空间，大小为两个已经排好序的子序列大小之和，该空间用来存放合并后的序列；
2、设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3、比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4、重复步骤3直到某一指针超出序列尾；
5、将剩下的元素直接复制到合并序列尾部；

具体的动画细节

上代码

时间复杂度 O（nlogn）

空间复杂度 O（n）

func MergeSort(arr []int) []int { 	if len(arr) <= 1 { 		return arr 	}  	mid := len(arr) / 2 	leftArr := MergeSort(arr[0:mid]) 	rightArr := MergeSort(arr[mid:]) 	return merge(leftArr, rightArr) }  func merge(left, right []int) []int { 	i, j := 0, 0 	m, n := len(left), len(right) 	var result []int 	// 合并子序列 	for { 		// 任何一个区间遍历完成就退出 		if i >= m || j >= n { 			break 		} 		if left[i] > right[j] { 			result = append(result, right[j]) 			j++ 		} else { 			result = append(result, left[i]) 			i++ 		} 	}  	// 左边的子集没有遍历完成，将左侧的放入到结果集 	if i < m { 		result = append(result, left[i:]...) 	}  	// 右侧的子集没有遍历完成，将右侧的放入到结果集中 	if j < n { 		result = append(result, right[j:]...) 	}  	return result }

直接在原数组上进行操作

func MergeSort(nums []int) []int { 	mergeSort(nums, 0, len(nums)-1) 	return nums }  func mergeSort(nums []int, start, end int) { 	if start >= end { 		return 	} 	mid := start + (end-start)/2 	mergeSort(nums, start, mid) 	mergeSort(nums, mid+1, end) 	var tmp []int 	i, j := start, mid+1 	for i <= mid && j <= end { 		if nums[i] > nums[j] { 			tmp = append(tmp, nums[j]) 			j++ 		} else { 			tmp = append(tmp, nums[i]) 			i++ 		} 	} 	if i <= mid { 		tmp = append(tmp, nums[i:mid+1]...) 	} 	if j <= end { 		tmp = append(tmp, nums[j:end+1]...) 	} 	for i := start; i <= end; i++ { 		nums[i] = tmp[i-start] 	} }

5、数组中的逆序对

题目地址：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

输入: [7,5,6,4] 输出: 5

解题思路

首先用到的是分治算法的思想

1、什么是逆序对，就是前面的数字大小，小于位于其后面的数字大小，那么这就是一个逆序对；

2、这里主要用到了分治的算法，只是在分治算法的基础之上，在进行数据的合并的时候，因为左边部分和右边部分都是已经排好序了，所以可以使用这种关系，来计算逆序对的个数；

3、具体的合并计算过程；

1、在左边和右边数组中，都从第一个下标，开始匹配；
2、如果左边当前下标的数大于右边数组当前下标的值，因为这两个数组都是从大到小排序的，所有左边从当前下标开始数，都大于右边当前匹配下标的数，cnt += mid - i + 1，同时右边数组下标前移；
3、如果左边当前下标的数小于右边数组当前下标的值，不满足，左边数组下标前移；

func reversePairs(nums []int) int { 	return mergeSort(nums, 0, len(nums)-1) }  func mergeSort(nums []int, start, end int) int { 	if start >= end { 		return 0 	} 	mid := start + (end-start)/2 	cnt := mergeSort(nums, start, mid) + mergeSort(nums, mid+1, end) 	tmp := []int{} 	i, j := start, mid+1 	for i <= mid && j <= end { 		if nums[i] > nums[j] { 			tmp = append(tmp, nums[j]) 			cnt += mid - i + 1 			j++ 		} else { 			tmp = append(tmp, nums[i]) 			i++ 		} 	}          if i <= mid {         tmp = append(tmp, nums[i:mid+1]...)     }     if j <= end{         tmp = append(tmp, nums[j:end+1]...)     } 	for i := start; i <= end; i++ { 		nums[i] = tmp[i-start] 	} 	return cnt }

6、汉诺塔

汉诺塔问题的描述：

假设有 A、B、C 三根柱子。其中在 A 柱子上，从下往上有 N 个从大到小叠放的盘子。我们的目标是，希望用尽可能少的移动次数，把所有的盘子由 A 柱移动到 C 柱。过程中，每次只能移动一个盘子，且在任何时候，大盘子都不可以在小盘子上面。

解题思路：

尝试把问题分解，使用分治的思想，将问题分解成一个个容易解决的子问题，然后一个个的去解决

我们把一个 N 层汉诺塔从 A 搬到 C，我们假定只有两层，首先把 N-1 层搬到 B,然后把下面的第 N 层搬到 C，然后再把 N-1 层从 B 搬到 C 。

如果存在多层，那我们就假定 N-1 层已经排好序了，只搬第 N 层，这样依次递归下去。

终止条件：

当只剩下最后一个的时候，我们只需要搬动一次就行了

var count int = 0  func main() { 	beadNum := 5 // This is the initial number of beads 	hanoi(beadNum, "A", "B", "C") 	fmt.Println(count) }  func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) { 	if beadNum == 1 { 		// 最后一个了，可以结束了 		move(beadNum, pillarA, pillarC) 	} else { 		// Step 2: 将 N-1 层从 A 移动到 B 		hanoi(beadNum-1, pillarA, pillarC, pillarB) 		// Step 2: 将第 N 层从 A 移动到 C 		move(beadNum, pillarA, pillarC) 		// Step 3: 将 B 中的 N-1 层移动到 C 		hanoi(beadNum-1, pillarB, pillarA, pillarC) 	} }  func move(beadNum int, pillarFrom string, pillarTo string) { 	count += 1 }