Python3合并两个有序数组代码实例

第一种思路，把两个数组合为一个数组然后再排序，问题又回归到冒泡和快排了，没有用到两个数组的有序性。（不好）

第二种思路，循环比较两个有序数组头位元素的大小，并把头元素放到新数组中，从老数组中删掉，直到其中一个数组长度为0。然后再把不为空的老数组中剩下的部分加到新数组的结尾。（好）

第二种思路的排序算法与测试代码如下：

def merge_sort(a, b):
  ret = []
  while len(a)>0 and len(b)>0:
    if a[0] <= b[0]:
      ret.append(a[0])
      a.remove(a[0])
    if a[0] >= b[0]:
      ret.append(b[0])
      b.remove(b[0])
  if len(a) == 0:
    ret += b
  if len(b) == 0:
    ret += a
  return ret

if __name__ == '__main__':
  a = [1,3,4,6,7,78,97,190]
  b = [2,5,6,8,10,12,14,16,18]
  print(merge_sort(a, b))

反思了一下上面的过程，不应该用remove方法，因为仔细想一下remove方法可能比较耗时，不算最简单。

改进一下，改用索引元素比较法替代头位元素比较法：

def merge_sort(a, b):
  ret = []
  i = j = 0
  while len(a) >= i + 1 and len(b) >= j + 1:
    if a[i] <= b[j]:
      ret.append(a[i])
      i += 1
    else:
      ret.append(b[j])
      j += 1
  if len(a) > i:
    ret += a[i:]
  if len(b) > j:
    ret += b[j:]
  return ret

if __name__ == '__main__':
  a = [1,3,4,6,7,78,97,190]
  b = [2,5,6,8,10,12,14,16,18]
  print(merge_sort(a, b))

这个基本就是最简单的方法了。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Python替换NumPy数组中大于某个值的所有元素实例

    我有一个2D(二维) NumPy数组,并希望用255.0替换大于或等于阈值T的所有值.据我所知,最基础的方法是: shape = arr.shape result = np.zeros(shape) for x in range(0, shape[0]): for y in range(0, shape[1]): if arr[x, y] >= T: result[x, y] = 255 有更简洁和pythonic的方式来做到这一点吗? 有没有更快(可能不那么简洁和/或不那么pythonic)的

  • 在python3中实现查找数组中最接近与某值的元素操作

    我就废话不多说了,直接上代码吧! import datetime def find_close(arr, e): start_time = datetime.datetime.now() size = len(arr) idx = 0 val = abs(e - arr[idx]) for i in range(1, size): val1 = abs(e - arr[i]) if val1 < val: idx = i val = val1 use_time = datetime.dateti

  • python由已知数组快速生成新数组的方法

    需求描述 在利用numpy进行数据分析时,常有的一个需求是:根据已知的数组生成新数组.这个问题又可以分为两类: 根据筛选条件生成子数组: 根据变换条件生成新数组(新数组shape与原数组相同) 下面简单总结. 生成子数组 情况1 已知数组a,以及若干筛选条件conds,要求从数组a中生成一个子数组b. 解决办法:b=a[conds].比如b=a[a>0],b=a[(a>=1)|(a<=-2)], b=a[(a>=1)&(a<=3)] 实例:如下 # 实例1.1:已知数

  • python如何建立全零数组

    语句格式: numpy.zeros(shape, dtype=float, order='C') 参数说明: shape:整型或元素为整型的序列,表示生成的新数组的shape,如(2,3)或 2. dtype:生成数组的数据格式,如numpy.int8.默认为numpy.float64. order:{'C', 'F'}可选,是否将多维数据存储为C-或Fortran-contiguous(按行或按列)顺序. 返回值:ndarray,一个指定了shape, dtype, order的零数组. 示例

  • Python 改变数组类型为uint8的实现

    第一次发博客,尝试一下 学习opencv3的时候,绘制hsv空间中的2d直方图,必须要将生成的hist数组的格式转换为uint8格式,否则应用cv2.imshow时图像不能显示! # data=np.array(hist,dtype='uint8') 补充知识:python中图片的float类型和uint8类型 在python图像处理过程中,遇到的RGB图像的值是处于0-255之间的,为了更好的处理图像,通常会将图像值转变到0-1之间 这个处理的过程就是图像的float类型转变为uint8类型过

  • python 实现多维数组(array)排序

    关于多维数组如何复合排序 如数组: >>> import numpy as np >>> data = np.array([[2,2,5],[2,1,3],[1,2,3],[3,1,4]]) >>>> data array([[2, 2, 5], [2, 1, 3], [1, 2, 3], [3, 1, 4]]) 将数组先按照第一列升序,第二列升序,第三列升序的方式排序: >>> idex=np.lexsort([data[:,

  • python对数组进行排序,并输出排序后对应的索引值方式

    废话不多说,直接上代码吧! # -*- coding: cp936 -*- import numpy as np #一维数组排序 arr = [1, 3, 5, 2, 4, 6] arr = np.array(arr) print arr print np.sort(arr)#或print np.sort(arr,axis=None) print (np.argsort(arr)) # 正序输出索引,从小到大 print (np.argsort(-arr)) # 逆序输出索引,从大到小 输出结果

  • Python3合并两个有序数组代码实例

    第一种思路,把两个数组合为一个数组然后再排序,问题又回归到冒泡和快排了,没有用到两个数组的有序性.(不好) 第二种思路,循环比较两个有序数组头位元素的大小,并把头元素放到新数组中,从老数组中删掉,直到其中一个数组长度为0.然后再把不为空的老数组中剩下的部分加到新数组的结尾.(好) 第二种思路的排序算法与测试代码如下: def merge_sort(a, b): ret = [] while len(a)>0 and len(b)>0: if a[0] <= b[0]: ret.appen

  • PHP实现合并两个有序数组的方法分析

    本文实例讲述了PHP实现合并两个有序数组的方法.分享给大家供大家参考,具体如下: $arr1 = array(1,2,3,4,5,6,7,8); $arr2 = array(3,4,5,7,9,10); //方法1 function mergeOrderly1($arr1,$arr2){ $i=0;$j=0; $int = array(); while($i<count($arr1) && $j<count($arr2)){ $int[] = $arr1[$i]<$arr

  • Python实现的合并两个有序数组算法示例

    本文实例讲述了Python实现的合并两个有序数组算法.分享给大家供大家参考,具体如下: 思路 按位循环比较两个数组,较小元素的放入新数组,下标加一(注意,较大元素对应的下标不加一),直到某一个下标超过数组长度时退出循环 假设两个源数组的长度不一样,那么假设其中短的数组用完了,即全部放入到新数组中去了,那么长数组中剩下的那一段就可以直接拿来放入到新数组中去了. #coding=utf-8 #合并数据 test1 = [1,2,5,7,9] test2=[2,4,6,8,10,11,34,55] d

  • go语言题解LeetCode88合并两个有序数组示例

    目录 题目描述 思路分析 AC 代码 题目描述 原题链接 : 88. 合并两个有序数组 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2,另有两个整数 m 和 n ,分别表示 nums1 和 nums2 中的元素数目. 请你 合并 nums2 到 nums1 中,使合并后的数组同样按 非递减顺序 排列. 注意:最终,合并后数组不应由函数返回,而是存储在数组 nums1 中.为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素

  • java实现把两个有序数组合并到一个数组的实例

    如下所示: package com.test.sort; public class testMerge { public static void main(String[] args) { int[] a = { 1, 3, 5 }; int[] b = { 2, 3, 4, 7 }; merge m = new merge(); m.method(a, b); } } class merge { public void method(int[] a, int[] b) { int l = a.

  • C++实现两个有序数组的合并

    本文实例为大家分享了C++实现两个有序数组合并的具体代码,供大家参考,具体内容如下 剑指offer面试题5延展题: 问题:有两个排序的数组A1和A2,内存在A1的末尾有足够多的空间容纳A2.请实现一个函数,把A2中所有数字插入A1中,并且所有的数字是排序(默认升序)的. 思路:在合并两个数组(包括字符串)时,从前往后复制每个数字(或字符)则需要重复移动数字(或字符)多次,则考虑从后往前复制就可以减少移动的次数,从而提高效率. 1.n1,n2分别指向数组A1和A2的尾部,strNew指向合并后的数

  • 浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    浅谈JAVA实现选择排序，插入排序，冒泡排序，以及两个有序数组的合并

    一直到大四才开始写自己的第一篇博客,说来实在有点羞愧.今天写了关于排序的算法题,有插入排序,冒泡排序,选择排序,以下贴上用JAVA实现的代码: public class test5 { public static void print(int []array) //输出数组方法 { for(int i=0;i<array.length;i++) System.out.print(" "+array[i]); } public static void selectsort(int

  • iOS常用算法之两个有序数组合并（要求时间复杂度为0(n)）

    思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去; 简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去. 代码如下: - (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 { // 全为空不处理 if (!array1.

  • Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归 (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同. eg:[1,2

  • python实现合并两个有序列表的示例代码

    python实现合并两个有序列表的示例代码

    题目描述 将两个升序链表合并为一个新的升序链表并返回.新链表是通过拼接给定的两个链表的所有节点组成的. LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 测试用例 示例1 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例2 输入:l1 = [], l2 = [] 输出:[] 示例3 输入:l1 = [], l2 = [0] 输出:[0] 代码详解 因为Lee

随机推荐