Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

数据结构和算法躬行记(7)——分治算法

咖啡机(K.F.J) 2020-10-12 05:58:00 阅读数:134 评论数:0 点赞数:0 收藏数:0

分治算法(Divide-and-Conquer Algorithm),就是分而治之,把一个复杂问题分成两个或更多个相同或相似的子问题,直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

分治算法比较适合用递归来实现,而每一层递归都会涉及三个操作:

(1)分解:将原问题分解为若干个规模较小,相对独立,与原问题形式相同的子问题,缩小问题规模。

(2)求解:若子问题规模较小且易于解决时(找出基线条件),则直接解。否则,递归地解决各子问题。其中基线条件(base case)通常是数组为空或只包含一个元素。

(3)合并:将各子问题的解合并为原问题的解。

分治算法是一种处理问题的思想和技巧,是很多高效算法的基础,例如排序算法(归并和快排)、最大公因数等。

LeetCode的169. 多数元素,可将数组一分为二,左边递归最大值(left),右边也一样(right),当两者相同,就是找到了;当不同时,比较谁的计数多。

与动态规划不同,分治算法分解的子问题可以独立求解,并且它们之间没有相关性。

在《剑指Offer》一书中曾提到,解决复杂问题的3种方法:

(1)画图,涉及链表、二叉树等数据结构时,画几张草图,可将隐藏的规律变得直观。

(2)举例,将抽象问题具体化,模拟运行过程,说不定能发现其中规律。

(3)分解,如果问题很大,则尝试把大问题分解成小问题,然后递归解决,分治法、动态规划等方法都是分解复杂问题的思路。

一、归并排序

利用递归与分治技术将数据序列划分成越来越小的半子表,再对半子表排序,最后用递归方法将排好序的半子表合并成为越来越大的有序序列,如下所示,思路如图8所示。

function mergeSort(arr) {
let len = arr.length;
//基线条件
if (len < 2) {
return arr;
}
//分解
let middle = Math.floor(len / 2),
left = mergeSort(arr.slice(0, middle)),
right = mergeSort(arr.slice(middle));
//合并
return merge(left, right);
}
function merge(left, right) {
let result = [];
//求解
while (left.length && right.length) {
//小的在左,大的在右
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}

图 8

面试题51 数组中的逆序对。先统计子数组中的逆序对,然后统计两个相邻数组之间的逆序对,在统计的过程中还需要对数组进行归并排序。

二、快速排序

采用“分而治之”的思想,把大的拆分为小的,小的再拆分为更小的。

将原序列分为两部分,其中前一部分的所有记录均比后一部分的所有记录小,然后再依次对前后两部分的记录进行快速排序,递归该过程,直到序列中的所有记录均有序为止。

代码实现如下所示,思路如图9所示。

function quickSort(arr) {
var length = arr.length;
//基线条件
if (length <= 1) {
return arr;
}
var base = arr[0],
left = [], //保存小于基准元素的记录
right = []; //保存大于基准元素的记录
//求解
for (let i = 1; i < length; i++) {
if (base > arr[i]) { //放入左边数组
 left.push(arr[i]);
} else { //放入右边数组
 right.push(arr[i]);
}
}
//分解
left = quickSort(left);
right = quickSort(right);
//合并
return left.concat([base], right);
}

图 9

面试题39 数组中出现次数超过一半的数字。问题转换为查找中位数,受快速排序的启发,当基准值的下标刚好是n/2时,那么就是中位数,否则在另外两部分中查找。

面试题40 最小的 k 个数。采用快速排序思想,基于数组第 k 个数字来调整,比 k 个数小的在左边,大的在右边。

 

版权声明
本文为[咖啡机(K.F.J)]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/strick/p/13392504.html

支付宝红包,每日可领(支付宝免费1-2元支付红包)