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

您的位置:首頁技術文章
文章詳情頁

python 實現在無序數組中找到中位數方法

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

一、問題描述

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

2例如:

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

3、算法思想:

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

平均時間復雜度為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('中位數 = %s' % data)

知識補充:python streaming 實現某個字段排序

一,hadoop streaming默認情況

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

2,streaming的一些參數如下:

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

二,python streaming 實現某個字段的排序

1, 輸入數據: 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 # 按照第三列逆序排列,可以根據想要的第幾段來選擇。-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

運行結果:

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

11 12 2211 311 211 4 111 1

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

標簽: Python 編程
相關文章:
主站蜘蛛池模板: 亿立分板机_曲线_锯片式_走刀_在线式全自动_铣刀_在线V槽分板机-杭州亿协智能装备有限公司 | 临朐空调移机_空调维修「空调回收」临朐二手空调 | 称重传感器,测力传感器,拉压力传感器,压力变送器,扭矩传感器,南京凯基特电气有限公司 | 注塑_注塑加工_注塑模具_塑胶模具_注塑加工厂家_深圳环科 | 锂电混合机-新能源混合机-正极材料混料机-高镍,三元材料混料机-负极,包覆混合机-贝尔专业混合混料搅拌机械系统设备厂家 | 环保袋,无纺布袋,无纺布打孔袋,保温袋,环保袋定制,环保袋厂家,环雅包装-十七年环保袋定制厂家 | wika威卡压力表-wika压力变送器-德国wika代理-威卡总代-北京博朗宁科技 | 短信通106短信接口验证码接口群发平台_国际短信接口验证码接口群发平台-速度网络有限公司 | 螺杆式冷水机-低温冷水机厂家-冷冻机-风冷式-水冷式冷水机-上海祝松机械有限公司 | 罐体电伴热工程-消防管道电伴热带厂家-山东沃安电气 | 回转窑-水泥|石灰|冶金-巩义市瑞光金属制品有限责任公司 | 塑钢件_塑钢门窗配件_塑钢配件厂家-文安县启泰金属制品有限公司 深圳南财多媒体有限公司介绍 | 食品无尘净化车间,食品罐装净化车间,净化车间配套风淋室-青岛旭恒洁净技术有限公司 | 杭州火蝠电商_京东代运营_拼多多全托管代运营【天猫代运营】 | 振动台-振动试验台-振动冲击台-广东剑乔试验设备有限公司 | 冷柜风机-冰柜电机-罩极电机-外转子风机-EC直流电机厂家-杭州金久电器有限公司 | 建筑消防设施检测系统检测箱-电梯**检测仪器箱-北京宇成伟业科技有限责任公司 | 河南卓美创业科技有限公司-河南卓美防雷公司-防雷接地-防雷工程-重庆避雷针-避雷器-防雷检测-避雷带-避雷针-避雷塔、机房防雷、古建筑防雷等-山西防雷公司 | 无硅导热垫片-碳纤维导热垫片-导热相变材料厂家-东莞市盛元新材料科技有限公司 | 金现代信息产业股份有限公司--数字化解决方案供应商 | 贝朗斯动力商城(BRCPOWER.COM) - 买叉车蓄电池上贝朗斯商城,价格更超值,品质有保障! | 杭州荣奥家具有限公司-浙江办公家具,杭州办公家具厂 | 首页|专注深圳注册公司,代理记账报税,注册商标代理,工商变更,企业400电话等企业一站式服务-慧用心 | 气动调节阀,电动调节阀,自力式压力调节阀,切断阀「厂家」-浙江利沃夫自控阀门 | 耐火浇注料价格-高强高铝-刚玉碳化硅耐磨浇注料厂家【直销】 | 蒸汽吸附分析仪-进口水分活度仪|康宝百科 | 金属检测机_金属分离器_检针验针机_食品药品金属检探测仪器-广东善安科技 | 卫生型双针压力表-高温防腐差压表-安徽康泰电气有限公司 | 微信小程序定制,广州app公众号商城网站开发公司-广东锋火 | 轻型地埋电缆故障测试仪,频响法绕组变形测试仪,静荷式卧式拉力试验机-扬州苏电 | 成都治疗尖锐湿疣比较好的医院-成都治疗尖锐湿疣那家医院好-成都西南皮肤病医院 | 啤酒设备-小型啤酒设备-啤酒厂设备-济南中酿机械设备有限公司 | 杭州公司变更法人-代理记账收费价格-公司注销代办_杭州福道财务管理咨询有限公司 | 预制直埋蒸汽保温管-直埋管道-聚氨酯发泡保温管厂家 - 唐山市吉祥保温工贸有限公司 | 丙烷/液氧/液氮气化器,丙烷/液氧/液氮汽化器-无锡舍勒能源科技有限公司 | 西安微信朋友圈广告投放_微信朋友圈推广_西安度娘网络科技有限公司 | 济宁工业提升门|济宁电动防火门|济宁快速堆积门-济宁市统一电动门有限公司 | 快速门厂家批发_PVC快速卷帘门_高速门_高速卷帘门-广州万盛门业 快干水泥|桥梁伸缩缝止水胶|伸缩缝装置生产厂家-广东广航交通科技有限公司 | 聚合氯化铝_喷雾聚氯化铝_聚合氯化铝铁厂家_郑州亿升化工有限公司 | 气力输送设备_料封泵_仓泵_散装机_气化板_压力释放阀-河南锐驰机械设备有限公司 | 智成电子深圳tdk一级代理-提供TDK电容电感贴片蜂鸣器磁芯lambda电源代理经销,TDK代理商有哪些TDK一级代理商排名查询。-深圳tdk一级代理 |