@
- 0. 相关博客
- 1. 视频题目
- 1.1 合并两个有序数组
- 1.1.1 描述
- 1.1.2 代码
- 1.1.3 总结
- 1.2 排序数组
- 1.2.1 描述
- 1.2.2 代码
- 1.2.3 总结
- 1.1 合并两个有序数组
- 2. 作业题目
- 2.1 有序数组的平方
- 2.1.1 描述
- 2.1.2 代码
- 2.1.3 总结
- 2.2 数组的相对排序
- 2.2.1 描述
- 2.2.1 代码
- 2.2.3 总结
- 2.3 对链表进行插入排序
- 2.3.1 描述
- 2.3.2 代码
- 2.3.3 总结
- 2.1 有序数组的平方
0. 相关博客
我在之前的Python程序员面试笔试宝典专栏的第4章_数据结构与算法（一）博客当中，总结过十大排序算法
1. 视频题目
1.1 合并两个有序数组
1.1.1 描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length==m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？
1.1.2 代码
本题要求的是在原数组上进行修改，否则直接新建一个数组，然后扫描两个原数组即可
原数组后面为空，两个数组有序，所以是从后往前扫描，并且从后往前插入原数组
class Solution:def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:"""Do not return anything, modify nums1 in-place instead."""i = m+n-1n1 = m-1n2 = n-1while n2>-1 and n1>-1:if nums1[n1]<nums2[n2]:# 如果是nums2的值更大nums1[i] = nums2[n2]n2 -= 1# nums2的指针左移弹出元素else:# 否则就是相等或者nums1更大nums1[i] = nums1[n1]n1 -= 1# 弹出nums1的元素i -= 1# 新数组的指针左移nums1[0:n2+1] = nums2[0:n2+1]# 如果nums2还有值的话
1.1.3 总结
可以从大到小，从后往前扫描，因为原数组的后面是空的
1.2 排序数组
1.2.1 描述
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104
1.2.2 代码
先来试试归并排序
class Solution:def merge(self,nums1,nums2):res = []while nums1 and nums2 :if nums1[0] < nums2[0]:res.append(nums1.pop(0))# 升序排列，先加入小的else:res.append(nums2.pop(0))res += nums1# 如果nums1非空就连接，此时nums2肯定为空res += nums2# 如果nums2非空就连接，此时nums1肯定为空return resdef mergeSort(self,nums):if len(nums)>1 :# 如果数组中至少两个元素mid = len(nums)//2# 求得中值，划分左右return self.merge(self.mergeSort(nums[0:mid]),self.mergeSort(nums[mid:]))# 合并排序后的左右数组else:return nums# 只有一个元素就认为是排序好的结果，直接返回def sortArray(self, nums: List[int]) -> List[int]:return self.mergeSort(nums)
快排的时候有点神奇，对于同一个思路：
class Solution:def quickSort(self,nums):if len(nums)>1:mid = len(nums)//2left = []right = []mid = nums.pop(mid)while nums:if nums[0]<mid:left.append(nums.pop(0))# 小的加入左边else:right.append(nums.pop(0))#大的加入右边，相等的也在右边return self.quickSort(left)+[mid]+self.quickSort(right)# 返回排序好的数组else:return nums# 只有一个元素则认为有序def sortArray(self, nums: List[int]) -> List[int]:return self.quickSort(nums)
上面的写法是超时的，下面的写法才正常
class Solution:def quickSortV1(self,array):if len(array) < 2:return array# 数组只有一个值则返回mid = array[len(array) // 2]# 选取基准，随便选哪个都可以left, right = [], []# 定义基准值左右两个数列array.remove(mid)# 从原始数组中移除基准值for item in array:if item >= mid:right.append(item)# 大于基准值放右边else:left.append(item)# 小于基准值放左边return self.quickSortV1(left) + [mid] + self.quickSortV1(right)# 递归对新数组的左右两边进行排序def sortArray(self, nums: List[int]) -> List[int]:return self.quickSortV1(nums)
应该是pop涉及到了对原数组的修改，所以比较耗费实践
1.2.3 总结
只有一个元素的数组被认为是有序的，这也是递归的出口
快排的时候不要修改原数组，很费时间的，用for遍历就好
2. 作业题目
2.1 有序数组的平方
2.1.1 描述
给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
示例 1：
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]
示例 2：
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]
提示：
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序
进阶：
请你设计时间复杂度为 O(n) 的算法解决本问题
2.1.2 代码
应该是分为正数序列和负数序列来处理，正序列左到右，负序列右到左，都保证平方后是递增
然后比较得出平方较小的那一个数字，将其平方值放入到结果的列表当中
如果序列未完结，则逐个平方后按升序方向合并进入结果数组
注意，这里的序列是否完结需要判断，不然后面数组的索引可能会出错
也就是说，要保证数组的索引是真实有效不越界的
class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:res = []i = 0while i<len(nums):if nums[i]<0:i+=1else:break# 找到第一位非负数if i > 0:j = i-1# 如果存在负数else:j = -1# 不存在负数则置为-1while -1<j and i<len(nums):# 当正负序列都有值if nums[j]**2 < nums[i]**2 :res.append(nums[j]**2)j -= 1# 负数的平方更小else :res.append(nums[i]**2)i += 1# 正数的平方更小if -1<j:res += [i**2 for i in nums[0:j+1]][::-1]# 负数序列未完结if i<len(nums):res += [i**2 for i in nums[i:len(nums)]]# 整数序列未完结return res
2.1.3 总结
在有序的前提下，正序列左到右平方，负序列右到左平方，都保证平方后是递增
像数组索引这种情况，一定要优先保证索引是真实有效的再去进行使用
2.2 数组的相对排序
2.2.1 描述
给你两个数组，arr1 和 arr2，arr2 中的元素各不相同，arr2 中的每个元素都出现在 arr1 中。
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例 1：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
示例 2:
输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
输出：[22,28,8,6,17,44]
提示：
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
2.2.1 代码
利用哈希映射的思想，我们给原数组赋予权重，然后根据映射的权重表进行排序，再还原
我们需要将arr2的数值放在前面，不在arr2的放在后面，也就是arr2的权重小于正常权重
我们对于正常数字，直接将其本身作为权重，而对于arr2，则根据顺序从-5000赋予权重
其实这个-5000也可以改为别的，只要使得arr2中最大的权重，小于正常数字最小的权重就好
正常数字最小应该是0，所以arr2的权重最大为-1
而arr2最长有1000位，所以起始权重最大为-1000
我们构造第一个字典dict1记录arr2及其对应权重，而dict2则记录各权重对应的数字
至于hashTable，是arr1各数字映射的权重表，对其进行排序再还原即可，能够处理重复值
class Solution:def quickSort(self,nums):if len(nums)>1:# 如果数组当中超过一个元素mid = nums.pop(len(nums)//2)left = []right = []for item in nums:if item < mid :left.append(item)else:right.append(item)return self.quickSort(left)+[mid]+self.quickSort(right)else:# 数组当中少于两个元素即为有序return numsdef relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:val = -5000hashTable = []dict1 = dict()# 记录arr2当中数值的权重val = -5000# 权重的数值for item in arr2:dict1[item] = valval += 1# 先出现的数字的权重更小hashTable = []# 记录arr1数字的权重，用于排序dict2 = dict()# 记录arr1权重对应的数字，用于还原for item in arr1:if item in arr2:# 如果在arr2当中hashTable.append(dict1[item])# 其权重就是dict1的权重dict2[dict1[item]] = item# 记录权重对应的数字else :# 不在arr2当中hashTable.append(item)# 其权重就是自身dict2[item] = item# 记录权重对应的数字sortedTable = self.quickSort(hashTable)# 对权重表进行排序return [dict2[item] for item in sortedTable]# 根据权重的排序结果，还原原数组
2.2.3 总结
无法直接对数字进行排序，我们可以考虑对其赋予权重，然后根据权重来排序
权重表的数字和原数组的值是一一对应的，所以即使是重复值也可以处理
2.3 对链表进行插入排序
2.3.1 描述
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2：
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]
提示：
列表中的节点数在 [1, 5000]范围内
-5000 <= Node.val <= 5000
2.3.2 代码
新建一个列表，然后扫描原列表，将数值插入到新列表的合适的位置
在新列表当中寻找合适的位置的时候，一般使用.next来与当前元素比较
class Solution:def insertionSortList(self, head: ListNode) -> ListNode:dummy = ListNode()dummy.next = headcur = head.nexthead.next = Nonewhile cur:curNext = cur.nextinsertP = dummywhile insertP.next and cur.val > insertP.next.val:insertP = insertP.nextcur.next = insertP.nextinsertP.next = curcur = curNextreturn dummy.next
2.3.3 总结
在新列表当中寻找合适的位置的时候，一般使用.next来与当前元素比较