电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術(shù)文章
文章詳情頁

python 實現(xiàn)在無序數(shù)組中找到中位數(shù)方法

瀏覽:6日期:2022-08-04 13:28:27

一、問題描述

1求一個無序數(shù)組的中位數(shù), (若數(shù)組是偶數(shù),則中位數(shù)是指中間兩個數(shù)字之和除以2,若數(shù)組是奇數(shù),則中位數(shù)是指最中間位置。要求:不能使用排序,時間復雜度盡量低

2例如:

lists = [3, 2, 1, 4] , 中位數(shù)為 = (2+3)/2 = 2.5lists = [3, 1, 2] , 中位數(shù)為 2

3、算法思想:

利用快速排序思想(但是并不是全部使用):任意挑選一個元素,以該元素為key, 劃分數(shù)組為兩個部分,如果左側(cè)數(shù)組長度剛好為(n-1)/2, 那么key就為中位數(shù), 若左側(cè)數(shù)組長度 < (n-1)/2 , 那么中位數(shù)點在右側(cè),反之,中位數(shù)在左側(cè)。然后進入相應(yīng)的一側(cè)繼續(xù)尋找中位

平均時間復雜度為O(n)

二、程序

class Solution(object): def findmedian(self, lists): if not lists or len(lists) == 0: return [] n = len(lists) if n % 2 == 0: a = self.partition(lists, n/2, 0, n-1) b = self.partition(lists, n/2-1, 0, n-1) mid = (lists[a]+lists[b])/ (2 * 1.0) return mid else: mid = self.partition(lists, n/2, 0, n-1) return lists[mid] def partition(self, lists, k, start, end): key = lists[start] left, right = start, end while left < right: while left < right and lists[right] > key: right = right - 1 lists[left] = lists[right] while left < right and lists[left] < key: left = left + 1 lists[right] = lists[left] lists[left] = key if left == k: return left elif left > k: return self.partition(lists, k, start, left-1) else: return self.partition(lists, k, left+1, end) if __name__ == '__main__': sol = Solution() lists = [2, 5, 4, 9, 3, 6, 8, 7, 1] # lists = [1, 2] data = sol.findmedian(lists) print('中位數(shù) = %s' % data)

知識補充:python streaming 實現(xiàn)某個字段排序

一,hadoop streaming默認情況

1,在hadoop streaming的默認情況下,是以t作為分隔符的,標準輸入時,每行的第一個t之前的內(nèi)容作為key,第一個t之后的內(nèi)容作為value。注意,如果一個t字符都沒有,那么整行作為key。

2,streaming的一些參數(shù)如下:

-D stream.map.output.field.separator :設(shè)置map輸出中key和value的分隔符 -D stream.num.map.output.key.fields : 設(shè)置map程序分隔符的位置,該位置之前的部分作為key,之后的部分作為value -D map.output.key.field.separator : 設(shè)置map輸出中key內(nèi)部的分割符-D num.key.fields.for.partition : 指定分桶時,key按照分隔符切割后,其中用于分桶key所占的列數(shù)(配合-partitioner org.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner 使用)-D stream.reduce.output.field.separator:設(shè)置reduce輸出中key和value的分隔符 -D stream.num.reduce.output.key.fields:設(shè)置reduce程序分隔符的位置

二,python streaming 實現(xiàn)某個字段的排序

1, 輸入數(shù)據(jù): cat data.txt (中間是tab鍵)

11 211 311 4 111 1

11 12 22

2,streaming程序如下:

vim sorted.sh

#!/bin/bashexport CURRENT=/home/chunhe.liao/hadoop_streaming/sort/usr/local/hadoop-2.6.3/bin/hadoop jar /usr/local/hadoop-2.6.3/share/hadoop/tools/lib/hadoop-streaming-2.6.3.jar -D stream.map.output.field.separator=’t’ -D stream.num.map.output.key.fields=3 -D mapreduce.job.output.key.comparator.class=org.apache.hadoop.mapreduce.lib.partition.KeyFieldBasedComparator -D mapreduce.partition.keycomparator.options=-k3,3nr # 按照第三列逆序排列,可以根據(jù)想要的第幾段來選擇。-input '/user/test/inputdata/datas3/data.txt' -output '/user/test/streaming/sorted_20180711' -mapper 'python mapper.py' -reducer 'python reducer.py' -file '$CURRENT/mapper.py' -file '$CURRENT/reducer.py'

(2) mapper.py

# -*- coding: utf-8 -*-import sys for line in sys.stdin: line = line.strip() print(’{0}’.format(line))

(3) reducer.py

# -*- coding: utf-8 -*-import sys for line in sys.stdin: line = line.strip() print('{0}'.format(line))

運行命令:

bash sorted.sh

運行結(jié)果:

hdfs dfs -cat /user/test/streaming/sorted_20180711/part-00000

11 12 2211 311 211 4 111 1

以上這篇python 實現(xiàn)在無序數(shù)組中找到中位數(shù)方法就是小編分享給大家的全部內(nèi)容了,希望能給大家一個參考,也希望大家多多支持好吧啦網(wǎng)。

標簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 杭州翻译公司_驾照翻译_专业人工翻译-杭州以琳翻译有限公司官网 组织研磨机-高通量组织研磨仪-实验室多样品组织研磨机-东方天净 | Dataforth隔离信号调理模块-信号放大模块-加速度振动传感器-北京康泰电子有限公司 | 众品地板网-地板品牌招商_地板装修设计_地板门户的首选网络媒体。 | 杭州可当科技有限公司—流量卡_随身WiFi_AI摄像头一站式解决方案 | 中图网(原中国图书网):网上书店,尾货特色书店,30万种特价书低至2折! | 明渠式紫外线杀菌器-紫外线消毒器厂家-定州市优威环保 | 生态板-实木生态板-生态板厂家-源木原作生态板品牌-深圳市方舟木业有限公司 | 烽火安全网_加密软件、神盾软件官网 | 成人纸尿裤,成人尿不湿,成人护理垫-山东康舜日用品有限公司 | 西门子伺服控制器维修-伺服驱动放大器-828D数控机床维修-上海涌迪 | 智慧旅游_智慧景区_微景通-智慧旅游景区解决方案提供商 | 宽带办理,电信宽带,移动宽带,联通宽带,电信宽带办理,移动宽带办理,联通宽带办理 | 太空舱_民宿太空舱厂家_移动房屋太空舱价格-豪品建筑 | 全自动过滤器_反冲洗过滤器_自清洗过滤器_量子除垢环_量子环除垢_量子除垢 - 安士睿(北京)过滤设备有限公司 | LED太阳能中国结|发光红灯笼|灯杆造型灯|节日灯|太阳能灯笼|LED路灯杆装饰造型灯-北京中海轩光电 | 深圳工程师职称评定条件及流程_深圳职称评审_职称评审-职称网 | 骨龄仪_骨龄检测仪_儿童骨龄测试仪_品牌生产厂家【品源医疗】 | 耐腐蚀泵,耐腐蚀真空泵,玻璃钢真空泵-淄博华舜耐腐蚀真空泵有限公司 | 阀门智能定位器_电液动执行器_气动执行机构-赫尔法流体技术(北京)有限公司 | 好物生环保网、环保论坛 - 环保人的学习交流平台 | 金属波纹补偿器厂家_不锈钢膨胀节价格_非金属伸缩节定制-庆达补偿器 | 机械加工_绞车配件_立式离心机_减速机-洛阳三永机械厂 | 大倾角皮带机-皮带输送机-螺旋输送机-矿用皮带输送机价格厂家-河南坤威机械 | 罗茨真空机组,立式无油往复真空泵,2BV水环真空泵-力侨真空科技 | 环球周刊网| 变压器配件,变压器吸湿器,武强县吉口变压器配件有限公司 | 翰墨AI智能写作助手官网_人工智能问答在线AI写作免费一键生成 | 二次元影像仪|二次元测量仪|拉力机|全自动影像测量仪厂家_苏州牧象仪器 | 微波消解仪器_智能微波消解仪报价_高压微波消解仪厂家_那艾 | 洁净实验室工程-成都手术室净化-无尘车间装修-四川华锐净化公司-洁净室专业厂家 | 移动厕所租赁|移动卫生间|上海移动厕所租赁-家瑞租赁 | 新密高铝耐火砖,轻质保温砖价格,浇注料厂家直销-郑州荣盛窑炉耐火材料有限公司 | 首页|专注深圳注册公司,代理记账报税,注册商标代理,工商变更,企业400电话等企业一站式服务-慧用心 | 找果网 | 苹果手机找回方法,苹果iPhone手机丢了找回,认准找果网! | 电动葫芦|手拉葫芦|环链电动葫芦|微型电动葫芦-北京市凌鹰起重机械有限公司 | 便携式表面粗糙度仪-彩屏硬度计-分体式粗糙度仪-北京凯达科仪科技有限公司 | 冷油器-冷油器换管改造-连云港灵动列管式冷油器生产厂家 | 新疆乌鲁木齐网站建设-乌鲁木齐网站制作设计-新疆远璨网络 | 创客匠人-让IP变现不走弯路 | 高光谱相机-近红外高光谱相机厂家-高光谱成像仪-SINESPEC 赛斯拜克 | 植筋胶-粘钢胶-碳纤维布-碳纤维板-环氧砂浆-加固材料生产厂家-上海巧力建筑科技有限公司 |