Python查找两个有序列表中位数的方法【基于归并算法】

本文实例讲述了Python查找两个有序列表中位数的方法。分享给大家供大家参考，具体如下：

今天做到的一个机试题目，很简单，这里简单记录一下：

我用的是归并的思想，当然还可以用递归的方法，下面是具体实现：

#!usr/bin/env python
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：找到两个有序列表的中位数
若列表总长度为奇数则直接返回中间下标的值
否则返回前一个值，如长度为6则返回下标为2处的值
'''
import random
def random_nums_genetor(max_value=1000, total=100):
  '''''
  生成随机数
  '''
  num_list=[]
  for i in range(total):
    num_list.append(random.randint(1,max_value))
  return num_list
def find_two_list_mid_num(num_list1,num_list2):
  '''''
  找到两个有序列表的中位数
  '''
  length1=len(num_list1)
  length2=len(num_list2)
  total=length1+length2
  if total%2==0:
    half=total/2-1
  else:
    half=total/2
  res_list=[]
  while len(num_list1) and len(num_list2):
    if num_list1[0]<num_list2[0]:
      res_list.append(num_list1.pop(0))
    else:
      res_list.append(num_list2.pop(0))
  if len(num_list1):
    res_list+=num_list1
  elif len(num_list2):
    res_list+=num_list2
  #print res_list
  print res_list[half]
  return res_list
if __name__ == '__main__':
  print "我们测试结果："
  num_list1=[1,2,5,7,12,45,67,100]
  num_list2=[11,34,77,90]
  res_list=find_two_list_mid_num(num_list1,num_list2)
  print res_list[5]
  print '--------------------------------------------------------'
  num_list1=random_nums_genetor(max_value=1000, total=10)
  num_list2=random_nums_genetor(max_value=100, total=7)
  res_list=find_two_list_mid_num(num_list1, num_list2)
  print res_list[8]

结果如下：

（代码摘自《Python Cookbook》）

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

您可能感兴趣的文章:

  • Python对两个有序列表进行合并和排序的例子
  • python 实现归并排序算法
  • Python编程中归并排序算法的实现步骤详解
  • python实现折半查找和归并排序算法
  • Python实现的归并排序算法示例
  • Python排序搜索基本算法之归并排序实例分析
  • Python数据结构与算法之列表（链表，linked list）简单实现
  • Python cookbook(数据结构与算法)通过公共键对字典列表排序算法示例
赞 (0)

相关推荐

  • Python数据结构与算法之列表（链表，linked list）简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python排序搜索基本算法之归并排序实例分析

    Python排序搜索基本算法之归并排序实例分析

    本文实例讲述了Python排序搜索基本算法之归并排序.分享给大家供大家参考,具体如下: 归并排序最令人兴奋的特点是:不论输入是什么样的,它对N个元素的序列排序所用时间与NlogN成正比.代码如下: # coding:utf-8 def mergesort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(lef

  • Python对两个有序列表进行合并和排序的例子

    假设有2个有序列表l1.l2,如何效率比较高的将2个list合并并保持有序状态,这里默认排序是正序. 思路是比较简单的,无非是依次比较l1和l2头部第一个元素,将比较小的放在一个新的列表中,以此类推,直到所有的元素都被放到新的列表中. 考虑2个列表l1 = [2], l2 = [1],如何将他们合并呢?(注意:下面实现会改变l1和l2本来的值) 复制代码 代码如下: def signle_merge_sort(l1, l2):    tmp = []    if l1[0] < l2[0]:  

  • Python编程中归并排序算法的实现步骤详解

    基本思想:归并排序是一种典型的分治思想,把一个无序列表一分为二,对每个子序列再一分为二,继续下去,直到无法再进行划分为止.然后,就开始合并的过程,对每个子序列和另外一个子序列的元素进行比较,依次把小元素放入结果序列中进行合并,最终完成归并排序. 归并操作过程: 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤3直到某一指针达到序列尾

  • Python cookbook(数据结构与算法)通过公共键对字典列表排序算法示例

    本文实例讲述了Python通过公共键对字典列表排序算法.分享给大家供大家参考,具体如下: 问题:想根据一个或多个字典中的值来对列表排序 解决方案:利用operator模块中的itemgetter()函数对这类结构进行排序是非常简单的. # Sort a list of a dicts on a common key rows = [ {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Be

  • python实现折半查找和归并排序算法

    python实现折半查找和归并排序算法

    今天依旧是学算法,前几天在搞bbs项目,界面也很丑,评论功能好像也有BUG.现在不搞了,得学下算法和数据结构,笔试过不了,连面试的机会都没有-- 今天学了折半查找算法,折半查找是蛮简单的,但是归并排序我就挺懵比,看教材C语言写的归并排序看不懂,后来参考了别人的博客,终于搞懂了. 折半查找 先看下课本对于 折半查找的讲解.注意了,折半查找是对于有序序列而言的.每次折半,则查找区间大约缩小一半.low,high分别为查找区间的第一个下标与最后一个下标.出现low>high时,说明目标关键字在整个有序

  • Python实现的归并排序算法示例

    Python实现的归并排序算法示例

    本文实例讲述了Python实现的归并排序算法.分享给大家供大家参考,具体如下: 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用. 将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为二路归并. Python实现代码如下: #-*- coding: UTF-8 -*- import numpy as np def Merge(a, f, m, l):

  • python 实现归并排序算法

    理论不多说: 复制代码 代码如下: #!/usr/bin/python import sys def merge(array, q, p, r): left_array = array[q:p+1] right_array = array[p+1:r+1] left_array_num = len(left_array) right_array_num = len(right_array) i, j , k= [0, 0, q] while i < left_array_num and j <

  • Python查找两个有序列表中位数的方法【基于归并算法】

    Python查找两个有序列表中位数的方法【基于归并算法】

    本文实例讲述了Python查找两个有序列表中位数的方法.分享给大家供大家参考,具体如下: 今天做到的一个机试题目,很简单,这里简单记录一下: 我用的是归并的思想,当然还可以用递归的方法,下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找到两个有序列表的中位数 若列表总长度为奇数则直接返回中间下标的值 否则返回前一个值,如长度为6则返回下标为2处的值 ''' import random def rando

  • 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

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

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

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

  • python实现两个一维列表合并成一个二维列表

    我就废话不多说了,直接上代码吧! >>> list1 = [1,2,3,4,4] >>> list2 = [2,3,4,5,2] >>> z = list(zip(list1,list2)) >>> z [(1, 2), (2, 3), (3, 4), (4, 5), (4, 2)] >>> z[1][1] 3 >>> z[0][1] 2 >>> z[2] (3, 4) 以上这篇p

  • Python查找最长不包含重复字符的子字符串算法示例

    Python查找最长不包含重复字符的子字符串算法示例

    本文实例讲述了Python查找最长不包含重复字符的子字符串算法.分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度.例如在"arabcacfr"中,最长的不包含重复字符的子字符串是"acfr",长度为4 采用字典的方法,最后输出所有最长字符的列表 算法示例: # -*- coding:utf-8 -*- #! python3 class Solution: def __init__(self):

  • Python查找文件中包含中文的行方法

    前言 近几天在做多语言版本的时候再次发现,区分各种语言真的是一件比较困难的事情,上一次做中文提取工具的就花了不少时间,这次决定用python试一试,结果写起来发现真是方便不少,自己整理了一下方便以后查找使用. 代码 #!/usr/bin/env python3 # -*- coding: utf-8 -*- # find the line of containing chinese in files __author__ = 'AlbertS' import re def start_find_

  • Python比较两个图片相似度的方法

    本文实例讲述了Python比较两个图片相似度的方法.分享给大家供大家参考.具体分析如下: 这段代码实用pil模块比较两个图片的相似度,根据实际实用,代码虽短但效果不错,还是非常靠谱的,前提是图片要大一些,太小的图片不好比较.附件提供完整测试代码和对比用的图片. 复制代码 代码如下: #!/usr/bin/python # Filename: histsimilar.py # -*- coding: utf-8 -*- import Image def make_regalur_image(img

  • Python计算两个日期相差天数的方法示例

    本文实例讲述了Python计算两个日期相差天数的方法.分享给大家供大家参考,具体如下: #!/usr/bin/python import time import sys def dateinput(): date = raw_input('please input the first date: ') return date def datetrans(tdate): spdate = tdate.replace("/","-") try: datesec = ti

  • python查找指定具有相同内容文件的方法

    本文实例讲述了python查找指定具有相同内容文件的方法.分享给大家供大家参考.具体如下: python代码用于查找指定具有相同内容的文件,可以同时指定多个目录 调用方式:python doublesdetector.py c:\;d:\;e:\ > doubles.txt # Hello, this script is written in Python - http://www.python.org # doublesdetector.py 1.0p import os, os.path,

随机推荐