电销如何介绍网站建设,广州网络营销外包怎样,域名解析错误连不上网,如何制作微信链接推广学习目标
掌握归并排序的基本原理使用python语言解答归并排序题目
归并排序
原理及过程
将两个有序的数组合并成一个有序数组称为从上往下分解#xff1a;把当前区间一分为二#xff0c;直至分解为若干个长度为1的子数组从上往下的合并#xff1a;两个有序的子区域两两向…学习目标
掌握归并排序的基本原理使用python语言解答归并排序题目
归并排序
原理及过程
将两个有序的数组合并成一个有序数组称为从上往下分解把当前区间一分为二直至分解为若干个长度为1的子数组从上往下的合并两个有序的子区域两两向上合并体现了分治思想稳定排序
复杂度
平均时间复杂度O(NlogN) 最坏时间复杂度O(NlogN)
归并排序合并过程 temp数组用于存储合并结果合并后拷贝回原数组 双指针法 初始分别指向两个有序区间的开始位置指针应该如何移动 当合并左右两个有序区间时分为以下几种情况 左区间、右区间都还有元素且当前左区间元素值大于右区间元素值左区间、右区间都还有元素且当前左区间元素值小于等于右区间元素值左区间元素值用完、右区间还剩有元素值右区间元素用完、左区间还剩有元素值。 算法代码实现过程
分解把当前区间一分为二分解点即中间点mid(start end) / 2求解分别递归左右两个子区间[start… end] 和[mid1 … end]进行归并排序递归的终结条件是子区间的长度为1合并使用双指针法将两个有序区间归并成一个临时有序区间[start … end]并将结果拷贝到原数组的区间[start …end]是原数组[start… end]变为有序。
def merge(nums, start, mid, end):# 使用双指针法将两个有序区间归并成一个临时有序区间i, j, temp start, mid 1, []while i mid and j end:if nums[i] nums[j]:temp.append(nums[i])i 1else:temp.append(nums[j])j 1while i mid:temp.append(nums[i])i 1while j end:temp.append(nums[j])j 1for i in range(len(temp)):nums[start i] temp[i]def mergesort(nums, start, end):if start end:returnmid (start end) 1mergesort(nums, start, mid) # 递归左区间mergesort(nums, mid 1, end) # 递归右区间merge(nums, start, mid, end)return numsnum_list [8, 4, 5, 7, 1, 3, 6, 2]
print(mergesort(num_list, 0, len(num_list)- 1))LCR 170. 交易逆序对的总数
https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
解法归并排序
class Solution:def reversePairs(self, record: List[int]) - int:self.cnt 0def merge(nums, start, mid, end):# 使用双指针法将两个有序区间归并成一个临时有序区间i, j, temp start, mid 1, []while i mid and j end:if nums[i] nums[j]:temp.append(nums[i])i 1else:self.cnt mid - i 1 #更新逆序对的个数temp.append(nums[j])j 1while i mid:temp.append(nums[i])i 1while j end:temp.append(nums[j])j 1for i in range(len(temp)):nums[start i] temp[i]def mergesort(nums, start, end):if start end:returnmid (start end) 1mergesort(nums, start, mid) # 递归左区间mergesort(nums, mid 1, end) # 递归右区间merge(nums, start, mid, end)mergesort(record, 0, len(record) - 1)return self.cnt315. 计算右侧小于当前元素的个数力扣题目
https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
排序二分解法 使用sorted_num数组按照从小到大的顺序存储当前已经遍历过的元素 倒序遍历nums数组中的各个元素n对于n完成以下迭代 迭代 通过二分法找到n在sorted_nums数组中的插入位置index这个index便是数组sorted_nums中在n右侧且小于n的元素的个数添加到ans中把n插入到sorted_nums这一有序数组中 输出由于sorted_nums是从右往左添加的因此最后输出的时候要重新调整回来
class Solution:def countSmaller(self, nums: List[int]) - List[int]:if not nums:return []# 按照从小到大的顺序存储当前已经遍历过的所有元素sorted_num []#存储最终结果ans []# 倒序遍历for n in nums[::-1]:# 通过二分法找到n在sorted_nums数组中的插入位置indexindex bisect.bisect_left(sorted_num, n)#把n插入到sorted_nums这一有序数组中bisect.insort(sorted_num, n)ans.append(index)#输出时顺序调整return ans[::-1]附录基础
python数据结构与算法理论基础专栏
数据结构与算法pythonhttp://t.csdnimg.cn/Gb6MN
程序 数据结构 算法而且在面试过程中这些是必考必问的内容。内容大纲基础数据结构树、链表、栈、队列等、常见算法排序算法、递归算法等。
专栏是基于python的基础知识是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念同时结合力扣题目也能更好的掌握这些知识达到在面试中游刃有余的效果。
python基础语法
python基础精讲 http://t.csdnimg.cn/HdKdi
本专栏主要针对python基础语法帮助学习者快速接触并掌握python大部分最重要的语法特征。 1、基本数据类型和变量 2、分支结构与循环结构 3、函数与异常处理 4、类与模块 5、文件读写
通过本专栏可以快速掌握python的基础语法。
