前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >20190516-归并排序

20190516-归并排序

作者头像
py3study
发布2020-01-16 15:06:55
2790
发布2020-01-16 15:06:55
举报
文章被收录于专栏:python3

合并两个有序数组中相同的数,输出到一个新的数组中

难度分类

简单

题目描述

合并两个有序数组中相同的数,输出到一个新的数组中

示例1:

输入:

nums1 = [1,2,3]

nums2 = [2,5,6]

输出:

[1,2]

示例2:

输入:

nums1 = [1,2,4,9]

nums2 = [1,3,4,7,9]

输出:

[1,4,9]

算法-1

  1. 定义一个空的结果列表来存储2个列表中相同的值
  2. 使用双指针,分别指向2个列表的头部依次取值,当取值结果相等的时候,将值插入结果列表中
  3. 当取值结果不同的时候移动指针指向的值较小的指针,使其指向下一位,然后继续比较
  4. 当其中一个指针指向列表的末尾的时候,证明已经将列表比较完成,此时返回结果,图解如下:

Step1:nums1_index指向nums1的1,nums2_index指向nums2的1,此时nums1_index指向的值与nums2_index指向的值相等,更新result, 移动指针nums1_index与nums2_index分别向后移动一位

Step2: nums1_index指向nums1的2,nums2_index指向nums2的3,此时nums1_index指向的值小于nums2_index指向的值,不相等,因此不更新result, 仅移动nums1_index指针

Step3: nums1_index指向nums1的4,nums2_index指向nums2的3,此时nums1_index指向的值大于nums2_index指向的值,不相等,因此不更新result, 仅移动nums2_index指针

Step4: nums1_index指向nums1的4,nums2_index指向nums2的4,此时nums1_index指向的值与nums2_index指向的值相等,更新result, 移动指针nums1_index与nums2_index分别向后移动一位

……

考点-1

  1. 归并排序
  2. 双指针

代码-1

def mergeTwoLists(nums1,nums2):     '''使用双指针,比较2个列表中的元素,如果相等则记录结果,如果不相等则挪动指针指向的值较小的列表指针,指向其下一位,直到其中一个指针指向列表的末尾'''     nums1_index = 0     nums2_index = 0     result = []     while nums1_index<len(nums1) and nums2_index<len(nums2):         if nums1[nums1_index]==nums2[nums2_index]:             result.append(nums1[nums1_index])             nums1_index+=1             nums2_index+=1         elif nums1[nums1_index]>nums2[nums2_index]:             nums2_index+=1         else:             nums1_index+=1 return result print(mergeTwoLists([1,2,3],[1,2,4])) print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))

算法-2

该题也可使用python的列表的切片特性来解答,具体步骤如下:

  1. 当2个列表非空的时候进行对比
  2. 当2个列表的第一个元素相等的时候,更新result,使用切片功能使2个列表的第一个元素弹出,第二个元素变成第一个元素
  3. 当2个列表的第一个元素不相等的时候,使用切片功能弹出较小值,然后重复1,2,3步知道其中一个列表为空为止
  4. While 循环和结束条件
  5. 列表切片

考点-2

def mergeTwoLists(nums1,nums2):     result = []     while nums1 and nums2:#当2个列表非空的时候进行对比         if nums1[0] == nums2[0]:#当2个列表的第一个元素相等的时候记录result,然后同时将2个列表的第一个元素弹出,使列表第二个元素变成列表的第一个元素再次重复比较             result.append(nums1[0])             nums1 = nums1[1:]             nums2 = nums2[1:]         elif nums1[0]>nums2[0]: #如果列表1的第一个元素大于列表2的第一个元素,则切片修改第二个列表,使列表2的第2个元素变成第一个元素,继续对比             nums2 = nums2[1:]         else:             nums1 = nums1[1:]     return result print(mergeTwoLists([1,2,3],[1,2,4])) print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))

算法-3

使用list的pop()函数,具体步骤同算法-2

考点-3

  1. list.pop()函数

代码-3

def mergeTwoLists(nums1,nums2):        '''遍历len(nums1)+len(nums2)次,当pop的时候报异常的时候结束遍历'''     result = []     for i in range((len(nums1)+len(nums2))):         try:             if nums1[0] == nums2[0]:#遍历的时候当两个列表的第1个元素相等的时候,将该元素插入结果列表,然后同时将2个列表的第一个元素弹出,让第二个元素变成第一个元素                 result.append(nums1.pop(0))                 nums2.pop(0)             elif nums1[0]>nums2[0]:# 如果列表1的第一个元素大于列表2的第一个元素,则将列表2中的第一个元素弹出,使列表2的第2个元素变成第一个元素,继续对比                 nums2.pop(0)             else:                 nums1.pop(0)         except:#当pop报错的时候证明某一个列表已经为空,已对比完2个列表,此时返回结果             return result print(mergeTwoLists([1,2,3],[1,2,4])) #输出[1,2] print(mergeTwoLists([1,2,4,9],[1,3,4,7,9]))#输出[1,4,9]

参考-归并排序算法

上述方法主体思想为归并排序,附归并排序合并2个有序链表的代码

def mergeTwoLists(nums1,nums2):     nums1_index = 0#列表1的指针     nums2_index = 0#列表2的指针     result = []     while nums1_index<len(nums1) and nums2_index<len(nums2):#定义2个指针,遍历2个列表         if nums1[nums1_index]==nums2[nums2_index]:#如果值相等,则将结果都插入result中,然后指针分别后移一位,比较列表的下一位             result.append(nums1[nums1_index])             result.append(nums2[nums2_index])             nums1_index+=1             nums2_index+=1         elif nums1[nums1_index]>nums2[nums2_index]:#如果其中有一个值大,则将较小的值插入result中,然后移动较小值的指针             result.append(nums2[nums2_index])             nums2_index+=1         else:             result.append(nums1[nums1_index])             nums1_index+=1     if nums1_index<len(nums1):         result+=nums1[nums1_index:]     else:         result+=nums2[nums2_index:]     return result print(mergeTwoLists([1,2,4,9],[1,3,4,7,9])) #输出[1, 1, 2, 3, 4, 4, 7, 9, 9]

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019/06/06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 合并两个有序数组中相同的数,输出到一个新的数组中
  • 难度分类
  • 题目描述
  • 算法-1
  • 考点-1
  • 代码-1
  • 算法-2
  • 考点-2
  • 算法-3
  • 考点-3
  • 代码-3
  • 参考-归并排序算法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档