Go语言数据结构和算法(三十四)分治算法
分治算法是将一个巨大的输入分解成若干个小块.在每个小块上解决问题.然后将分段
解决方案合并为全局解决方案.
1.步骤:
分解:将原始问题分解成一组子问题.
解决子问题:递归的单独解决每个子问题.
合并子问题:将子问题的解放在一起得到整个问题的解.
2.应用:
2.1快速排序:
又称分区交互排序.是最有效率的排序算法.它首先从数组中选择一个枢轴值.然后将剩
下的数组元素分成两个子数组.通过将每个元素与枢轴值进行比较来进行分区.它比较
元素是否具有比枢轴值更大或更小的值.然后递归的对数组进行排序.
2.2归并排序:
这是通过比较对数组进行排序的算法.它首先将数组划分为子数组.然后递归对的对每
个子数组进行排序.排序完成后.将它们合成一个数组.
2.3二分搜索:
二分搜索是一种搜索算法.也称为半区间搜索或对数搜索.它将目标值与排序数组中存
在的中间元素进行比较.比较后.如果数值不同.则最终剔除不能包含目标的那一半数
组.在继续寻找另一半数组.直到找到目标值.如果搜索另一半也找不到.则断定目标值
不在数组中.
2.4最近点问题:
强调在给定n个点的情况下.找出度量空间中最近的一对点.使得这对点之间的距离应
该最小.
2.5Kadane算法:
该算法是解决最大子数组问题的有效算法.该问题是在整数数组中找到最大和的连续
子数组的任务.
2.6平衡二叉树构造:
给定一个排序的整数数组.任务是构造一个平衡二叉树.可以使用递归构造根节点的左
右子树的分治算法来解决.
3.点对点实现:
3.1方法:
package data import ( "math" "sort" ) func ClosestPair(points [][]int) float64 { h := make(helper, len(points)) for i, v := range points { //计算两点之间的距离. h[i] = [2]float64{math.Hypot(float64(v[0]), float64(v[1])), float64(i)} } //将数组按照升序排序. sort.Sort(h) if len(h) >= 1 { return h[0][0] } return 0 } type helper [][2]float64 func (h helper) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h helper) Less(i, j int) bool { return h[i][0] < h[j][0] } func (h helper) Len() int { return len(h) }3.2main方法:
func main() { points := [][]int{{3, 3}, {5, -1}, {-2, 4}} pair := data.ClosestPair(points) fmt.Println(pair) }4.实战:
4.1方法:
func ClosestPair2(points [][]int, k int) [][]int { if len(points) == k { return points } var v []int var re [][]int m := make(map[int]int) for i := 0; i < len(points); i++ { m[i] = points[i][0]*points[i][0] + points[i][1]*points[i][1] v = append(v, i) } closestUtil(m, v, 0, len(v)-1, k) for i := 0; i < k; i++ { re = append(re, points[v[i]]) } return re } func closestUtil(m map[int]int, s []int, start int, end int, k int) { p := m[s[end]] l := start for i := start; i < end; i++ { if m[s[i]] < p { s[l], s[i] = s[i], s[l] l++ } } s[l], s[end] = s[end], s[l] if k == l { return } else if l < k { closestUtil(m, s, l+1, end, k) } else { closestUtil(m, s, start, l-1, k) } }4.2main方法:
func main() { points := [][]int{{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}} k := 2 res := data.ClosestPair2(points, k) fmt.Println(res) }忽然世界开始变得很慢.时间也变得很慢.
如果大家喜欢我的分享的话.可以关注我的微信公众号
念何架构之路