广告区

广告区


本站消息

站长简介/公众号

关注本站官方公众号:程序员总部,领取三大福利!
福利一:python和前端辅导
福利二:进程序员交流微信群,专属于程序员的圈子
福利三:领取全套零基础视频教程(python,java,前端,php)

  价值13000svip视频教程,python大神匠心打造,零基础python开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-07(3)

2021-08(6)

python算法日记(归并排序)_leetcode 148. 排序链表 912. 排序数组

发布于2020-03-08 21:31     阅读(1130)     评论(0)     点赞(2)     收藏(0)



912. 排序数组

给定一个整数数组 nums,将该数组升序排列。

示例 1:

输入:[5,2,3,1]
输出:[1,2,3,5]
示例 2:

输入:[5,1,1,2,0,0]
输出:[0,0,1,1,2,5]

提示:

1 <= A.length <= 10000
-50000 <= A[i] <= 50000

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/sort-list

用归并排序的方法来做:

  1. class Solution:
  2. def sortArray(self, nums: List[int]) -> List[int]:
  3. if len(nums)==1: #递归边界:数组长度为1时返回
  4. return nums
  5. mid = len(nums)//2 #递归一直分成两半,直到分成左右(1,1),或左右(1,2)or(2,1),则1的直接返回,2的再分成(1,1)
  6. pre = nums[:mid]
  7. tail= nums[mid:]
  8. left = self.sortArray(pre)
  9. right = self.sortArray(tail)
  10. res = [] #用于装合并后的有序数组
  11. while left and right: # 合并,左右(1,1)合并时,把小的装进去,大的由下面if装
  12. if left[0]<=right[0]:
  13. res.append(left.pop(0)) #left,right长大于1时,注意从第一个开始比
  14. else:
  15. res.append(right.pop(0)) #注意装完要轮空,不然会死循环
  16. if left: #用来处理while后剩下的一个
  17. res+=left
  18. if right:
  19. res+=right
  20. return res

归并的思想,先一直分成两半,再排序合并起来。代码中通过while以下部分合并

示例2过程:

       [5,1,1,2,0,0]

分  [5,1,1]   [2,0,0]

分 [5] [1,1] [2] [0,0]

分 [5]  [1][1]  [2]  [0][0]

合       [1,1]        [0,0]          # [1,1]返回给right和left[5]一起进入while,right[0,0]和left[2]同理

合 [1,1,5]       [0,0,2]

合    [0,0,1,1,2,5]

也可以把合并单独写成一个函数:

  1. class Solution:
  2. def sortArray(self, nums: List[int]) -> List[int]:
  3. def marge(left, right):
  4. res = []
  5. while left and right:
  6. # 左右两个数列第一个最小放前面
  7. if left[0] <= right[0]:
  8. res.append(left.pop(0))
  9. else:
  10. res.append(right.pop(0))
  11. # 只有一个数列中还有值,直接添加
  12. res += left
  13. res += right
  14. return res
  15. if len(nums) == 1:
  16. return nums
  17. mid = len(nums) // 2
  18. left = nums[:mid]
  19. right = nums[mid:]
  20. return marge(self.sortArray(left), self.sortArray(right))

 有了912题的经验,148就比较容易了:

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. # def __init__(self, x):
  4. # self.val = x
  5. # self.next = None
  6. class Solution:
  7. def sortList(self, head: ListNode) -> ListNode:
  8. if not head or not head.next: # 链表为空的情况直接返回not head.next类似于数组长度为1
  9. return head
  10. slow = head #用快慢指针把链表分成两半
  11. fast = head.next
  12. while(fast and fast.next):
  13. slow = slow.next
  14. fast = fast.next.next
  15. tmp = slow.next
  16. slow.next = None #把前半部分的尾巴置空
  17. left = self.sortList(head)
  18. right = self.sortList(tmp)
  19. cur = res = ListNode(0) #用一个新链表装排序后合并的部分
  20. while left and right:
  21. if left.val<=right.val:
  22. cur.next = left
  23. left = left.next #加入后置空或用下一位进入比较
  24. else:
  25. cur.next = right
  26. right = right.next
  27. cur = cur.next
  28. cur.next = left or right #把while过后剩下的接上去
  29. return res.next

示例二过程:

       -1->5->3->4->0

分  -1->5        3->4->0

分  -1   5        3    4->0

分 -1   5         3    4   0

合 -1->5         3   0->4

合 -1->5         0->3->4

合  -1->0->3->4->5







所属网站分类: 技术文章 > 博客

作者:我Lovepython

链接:https://www.pythonheidong.com/blog/article/248501/35e05e77b32666be1ebc/

来源:python黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

2 0
收藏该文
已收藏

评论内容:(最多支持255个字符)