目录

1.排序问题1.2 选择排序查看答案错误版本正确版本 2. 最大子序和

1.排序问题

https://leetcode-cn.com/problems/sort-an-array/ ##1.1 冒泡排序

class Solution: def sortArray(self, nums: List[int]) -> List[int]: ## 冒泡排序 # 轮次 for i in range(len(nums)-1): # 趟 for j in range(len(nums)-i-1): if nums[j] > nums[j+1]: nums[j],nums[j+1] = nums[j+1],nums[j] return nums

但是运行结果却是超出时间限制。时间复杂度：$O(n^2)$

1.2 选择排序

class Solution: def sortArray(self, nums: List[int]) -> List[int]: ## 选择排序 for i in range(len(nums)): max_ind = 0 for j in range(len(nums)-i): if nums[j] > nums[max_ind]: max_ind = j nums[-1*(i+1)],nums[max_ind] = nums[max_ind],nums[-1*(i+1)] return nums

运行结果依然超出时间限制。时间复杂度：$O(n^2)$

查看答案

官方提供的解法是：快速排序、堆排序、归并排序。 快速排序的时间复杂度是$O(nlog(n))$。 快速排序的思路是先随机选择一个基准（pivot），把小于基准的放在左边，大于基准的放在右边。然后基准的左右也各种按照这种思路进行递归，直到子数列为1个，无需排序。 参考：https://baijiahao.baidu.com/s?id=1635285231673698375&wfr=spider&for=pc

错误版本

class Solution: def sortArray(self, nums: List[int]) -> List[int]: ## 快速排序 def quick_sort(sub_list): if len(sub_list) < 2: return sub_list else: pivot = sub_list[0] left = [] right = [] for i in range(1,len(sub_list)): if i <= pivot: left.append(i) else: right.append(i) return quick_sort(left) + [pivot] + quick_sort(right) return quick_sort(nums)

错误分析：没有分清楚index和data，把i混用了。

正确版本

class Solution: def sortArray(self, nums: List[int]) -> List[int]: ## 快速排序 def quick_sort(sub_list): if len(sub_list) < 2: return sub_list else: pivot = sub_list[0] left = [] right = [] for i in range(1,len(sub_list)): if sub_list[i] <= pivot: left.append(sub_list[i]) else: right.append(sub_list[i]) return quick_sort(left) + [pivot] + quick_sort(right) return quick_sort(nums)

感受：之前总觉得冒泡排序、选择排序傻傻分不清楚，好难啊。经过之前的思路学习，明确了每一步是做什么，这次写代码前先回顾一下上次的思路笔记，然后按部就班地写，写完后意外地发现：这么短吗？原来这么简单就实现了吗？ 对于 i 是作为index，还是data，脑海中要有个意识。不动手去做，永远不知道自己会犯怎样的低级错误。

2. 最大子序和

https://leetcode-cn.com/problems/maximum-subarray/

class Solution: def maxSubArray(self, nums: List[int]) -> int: ## 动态规划 # 新列表记录子序和 sum_list=[] sum_list.append(nums[0]) for i in range(1,len(nums)): if sum_list[i-1]+nums[i] > nums[i]: sum_list.append(sum_list[i-1] + nums[i]) else: sum_list.append(nums[i]) # 找出最大值 max_sum = sum_list[0] for i in range(1,len(sum_list)): if sum_list[i] > max_sum: max_sum = sum_list[i] return max_sum