分而治之

  • 最后更新:2018年12月01

分而治之法是一种算法范式。典型的分治算法采用以下三个步骤来解决问题。

  1. 分:将给定的问题分解成同类型的子问题。
  2. 征服递归地解决这些子问题
  3. 结合:正确组合答案

分而治之的一个经典例子是归并排序下面的演示。在归并排序中，我们把数组分成两半，递归地排序，然后归并排序后的两半。
Merge-Sort-Tutorial

关于分而治之的最新文章

主题:



标准算法:

  1. 分而治之论
  2. 二分查找
  3. 随机二叉搜索算法
  4. 归并排序
  5. 快速排序
  6. 铺瓷砖问题
  7. 计算反演
  8. 计算战俘(x, n)
  9. 最接近点对
  10. 最接近点对|o (nlogn)实现
  11. 用两个多项式
  12. Strassen矩阵乘法
  13. 天际线的问题
  14. 最大的子数组求和
  15. 最长公共前缀
  16. 在按行和按列排序的2D数组中搜索
  17. 快速乘法的空手道算法
  18. 凸包(简单分治算法)
  19. 凸包的快速包算法
  20. 子数组中不同元素使用Mo算法

基于二分查找的:

  1. 两个排序数组的中位数
  2. 两个不同大小的排序数组的中位数
  3. 排序数组中的层
  4. 找到数组中最接近的数字
  5. 在给定数组中找到一个固定点
  6. 查找给定数组中的峰值元素
  7. 检查排序数组中的多数元素
  8. 两个排序数组的第k个元素
  9. 找到旋转排序数组中的旋转计数
  10. 找到排序和旋转数组中的最小元素
  11. 找出大小为n的排序数组中唯一重复的元素
  12. 查找一个排序数组中存在的额外元素的索引
  13. 查找在排序数组中出现一次的元素
  14. 计数排序数组中出现的次数(或频率)
  15. 找出数组中先增后减的最大元素
  16. 减少和征服
  17. 使用pthread进行二进制搜索
  18. 单链表上的二元搜索
  19. 油漆工的隔断问题
  20. 画家的分区问题|集合2
  21. 求出0的个数
  22. 阶乘以n个0结尾的数
  23. 找到等差数列中缺失的数
  24. 数天后，水箱将变成空的
  25. 在给定的二进制序列中找到二进制点
  26. 找出单调递增函数第一次变为正的点

Misc:

  1. 河内迭代塔
  2. 河内塔项目
  3. 一个整数的平方根
  4. 求一个数的三次方根
  5. 分配最小页数
  6. 用最少的步骤收集所有的硬币
  7. 模幂运算(模算术中的幂)
  8. 找到二维数组中的峰值元素
  9. 程序计数在一个(大)数组中设置位的数目
  10. 使用最小比较次数的数组的最大值和最小值
  11. 在小于O(n)的时间内找出有限范围数组中每个元素的频率
  12. 包含矩阵每一行元素的数组相邻元素之间的最小差值
  13. 在排序矩阵中搜索元素
  14. 记住斯特拉森矩阵方程的简单方法
  15. 直方图中最大的矩形面积
  16. 分治递归的高级主定理
  17. 放置k个元素使最小距离最大化
  18. 多项式乘法的迭代快速傅里叶变换
  19. 编写自己的Power，不使用乘法(*)和除法(/)运算符
  20. 给定长度的序列，其中每个元素都大于或等于前一个元素的两倍
  21. Shuffle 2n个整数，格式为{a1, b1, a2, b2, a3, b3， ......， an, bn}，不使用额外的空间

快速链接:

如果你喜欢Geeksfo188金宝搏滚球投注rGeeks，并愿意做出贡献，你也可以写一篇文章，并将文章发送到contribute@geeksforgeeks.org。金宝搏比分看到你的文章出现在GeeksforGeeks主页上，并帮助其他极客。188金宝搏滚球投注

如果你发现任何不正确的地方，或者你想分享关于上面讨论的话题的更多信息，请写评论。




我个人的笔记 arrow_drop_up