通辽市城乡建设局网站,菜鸟教程网站建设,淘宝搜索关键词排名查询工具,门窗 东莞网站建设分治法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题#xff0c;这些子问题相互独立且与原问题性质相同。求出子问题的解#xff0c;就可得到原问题的解。即一种分目标完成程序算法#xff0c;简单问题可用二分法完成。
分治法解题的一般步骤#…分治法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题这些子问题相互独立且与原问题性质相同。求出子问题的解就可得到原问题的解。即一种分目标完成程序算法简单问题可用二分法完成。
分治法解题的一般步骤
分解将要解决的问题划分成若干规模较小的同类问题求解当子问题划分得足够小时用较简单的方法解决合并按原问题的要求将子问题的解逐层合并构成原问题的解。
实现方法分治法一般是通过递归调用实现的。例如排序算法(快速排序归并排序)傅里叶变换(快速傅里叶变换)等。
分治法使用场景
该问题的规模缩小到一定的程度就可以容易的解决。该问题可以分解为若干个规模较小的相同问题即该问题具有最优子结构性质。利用该问题分解出的子问题的解可以合并为该问题的解。该问题所分解出的各个子问题是相互独立的即子问题之间不包含公共的子问题。
第一条特征是绝大多数问题可以满足的问题的复杂性一般是随着问题规模的增加而增加第二条特征是应用分治法的前提。它是大多数问题可以满足的此特征反映了递归思想的应用。第三条特征是关键能否利用分治法完全取决于问题是否具有第三条特征如果具备了第一条和第二条而不具备第三条特征则可以考虑使用贪心法或者动态规划法。第四条关系到分治法的效率如果各个子问题是不独立的则分治法要做寻多不必要的工作重复的解决公共的子问题此时虽然可用分治法但一般使用动态规划法较好。
归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组再合并数组。
将数组分解最小之后然后合并两个有序数组基本思路是比较两个数组的最前面的数谁小就先取谁取了后相应的指针就往后移一位。然后再比较直至一个数组为空最后把另一个数组的剩余部分复制过来即可。
def merge_sort(alist):# 终止条件if len(alist) 1:return alist# 二分分解num len(alist)//2left merge_sort(alist[:num])right merge_sort(alist[num:])# 合并return merge(left,right)def merge(left, right):合并操作将两个有序数组left[]和right[]合并成一个大的有序数组#left与right的下标指针l, r 0, 0result []while llen(left) and rlen(right):if left[l] right[r]:result.append(left[l])l 1else:result.append(right[r])r 1result left[l:]result right[r:]return resultalist [54,26,93,17,77,31,44,55,20]
sorted_alist merge_sort(alist)
print(sorted_alist)#时间复杂度O(nlogn)运行结果 [17, 20, 26, 31, 44, 54, 55, 77, 93]
快速排序
快速排序英语Quicksort又称划分交换排序partition-exchange sort通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
步骤为
从数列中挑出一个元素称为基准pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区结束之后该基准就处于数列的中间位置。这个称为分区partition操作。递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形是数列的大小是零或一也就是永远都已经被排序好了。虽然一直递归下去但是这个算法总会结束因为在每次的迭代iteration中它至少会把一个元素摆到它最后的位置去。 # 快速排序
# 思路寻抓元素的正确位置左边的元素都小于该元素右边的都大于该元素
# 移动游标lowhigh不动则交换直到相遇(可同时交换也可异步交换)
def quick_sort(alist,first,end):# 终止条件if first end:returnn len(alist)mid_value alist[first]low firsthigh endwhile low high:# 注意处理特殊情况遇到相等的元素放在一边处理while low high and alist[high] mid_value:high - 1alist[low] alist[high]# low 1while low high and alist[low] mid_value:low 1alist[high] alist[low]# high - 1# 代码执行到此alist[0]找到正确位置解析来把划分出来的两段新列表递归执行alist[low] mid_value# 递归部分# 对基准元素左边的子序列进行快速排序quick_sort(alist,first,low-1)# 对基准元素右边的子序列进行快速排序quick_sort(alist,low1,end)alist [54,26,93,17,77,31,44,55,20]
quick_sort(alist,0,len(alist)-1)
print(alist)运行结果[17, 20, 26, 31, 44, 54, 55, 77, 93]
多数元素
给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。 class Solution:def majorityElement(self, nums: List[int]) - int:# 该题分治法不是最优解但是很好的练习return self.getmajrity(nums,0,len(nums)-1)def getmajrity(self,nums,left,right):# 终止条件if left right:return nums[left]mid left (right - left) // 2leftmajrity self.getmajrity(nums,left,mid)rightmajrity self.getmajrity(nums,mid1,right)#--------------- 此处为分界线上部分为分下部分为并----------------------# 当左边的多数元素 与 右边的多数元素相等时返回其中任一值如左边if leftmajrity rightmajrity: # 算是一个小优化(可以不要)return leftmajrity# # 如果不相等需要分别计算左右两边然后比较leftcount,rightcount 0,0for i in nums[left:right1]: ## 这里需要1 否则nums[right]取不到if i leftmajrity:leftcount 1elif i rightmajrity:rightcount 1if leftcount rightcount:return leftmajrityelse:return rightmajrity 最大子序列和
给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。
class Solution:def maxSubArray(self, nums: List[int]) - int:n len(nums)#递归终止条件if n 1:return nums[0]mid len(nums) // 2#递归计算左半边最大子序和max_left self.maxSubArray(nums[:mid])#递归计算右半边最大子序和max_right self.maxSubArray(nums[mid:])# -----------分界线 上面为分 下面为并----------------------------#计算中间的最大子序和从右到左计算左边的最大子序和从左到右计算右边的最大子序和再相加max_l nums[mid - 1]tmp 0for i in range(mid - 1, -1, -1):tmp nums[i]max_l max(tmp, max_l)max_r nums[mid]tmp 0for i in range(mid, len(nums)):tmp nums[i]max_r max(tmp, max_r)#返回三个中的最大值return max(max_right,max_left,max_lmax_r)
参考资料
leetcode 官网 https://zhuanlan.zhihu.com/p/72734354
