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

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

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

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

一、問(wèn)題描述

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

2例如:

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

3、算法思想:

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

平均時(shí)間復(fù)雜度為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)

知識(shí)補(bǔ)充:python streaming 實(shí)現(xiàn)某個(gè)字段排序

一,hadoop streaming默認(rèn)情況

1,在hadoop streaming的默認(rèn)情況下,是以t作為分隔符的,標(biāo)準(zhǔn)輸入時(shí),每行的第一個(gè)t之前的內(nèi)容作為key,第一個(gè)t之后的內(nèi)容作為value。注意,如果一個(gè)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 : 指定分桶時(shí),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 實(shí)現(xiàn)某個(gè)字段的排序

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ù)想要的第幾段來(lái)選擇。-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))

運(yùn)行命令:

bash sorted.sh

運(yùn)行結(jié)果:

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

11 12 2211 311 211 4 111 1

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

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 新能源汽车电机定转子合装机 - 电机维修设备 - 睿望达 | 培训中心-海南香蕉蛋糕加盟店技术翰香原中心官网总部 | BHK汞灯-百科|上海熙浩实业有限公司| 螺旋压榨机-刮泥机-潜水搅拌机-电动泥斗-潜水推流器-南京格林兰环保设备有限公司 | 扒渣机厂家_扒渣机价格_矿用扒渣机_铣挖机_撬毛台车_襄阳永力通扒渣机公司 | 分轨 | 上传文件,即刻分离人声和伴奏| 环氧乙烷灭菌器_压力蒸汽灭菌器_低温等离子过氧化氢灭菌器 _低温蒸汽甲醛灭菌器_清洗工作站_医用干燥柜_灭菌耗材-环氧乙烷灭菌器_脉动真空压力蒸汽灭菌器_低温等离子灭菌设备_河南省三强医疗器械有限责任公司 | 别墅图纸超市|别墅设计图纸|农村房屋设计图|农村自建房|别墅设计图纸及效果图大全 | 安德建奇火花机-阿奇夏米尔慢走丝|高维|发那科-北京杰森柏汇 | 优考试_免费在线考试系统_培训考试系统_题库系统_组卷答题系统_匡优考试 | 高中学习网-高考生信息学习必备平台| BESWICK球阀,BESWICK接头,BURKERT膜片阀,美国SEL继电器-东莞市广联自动化科技有限公司 | 压力控制器,差压控制器,温度控制器,防爆压力控制器,防爆温度控制器,防爆差压控制器-常州天利智能控制股份有限公司 | YT保温材料_YT无机保温砂浆_外墙保温材料_南阳银通节能建材高新技术开发有限公司 | 钢衬玻璃厂家,钢衬玻璃管道 -山东东兴扬防腐设备有限公司 | 骨灰存放架|骨灰盒寄存架|骨灰架厂家|智慧殡葬|公墓陵园管理系统|网上祭奠|告别厅智能化-厦门慈愿科技 | 通用磨耗试验机-QUV耐候试验机|久宏实业百科 | 健康管理师报名入口,2025年健康管理师考试时间信息网-网站首页 塑料造粒机「厂家直销」-莱州鑫瑞迪机械有限公司 | 南溪在线-南溪招聘找工作、找房子、找对象,南溪综合生活信息门户! | 武汉创亿电气设备有限公司_电力检测设备生产厂家 | 玄米影院| 欧景装饰设计工程有限公司-无锡欧景装饰官网 | 防渗土工膜|污水处理防渗膜|垃圾填埋场防渗膜-泰安佳路通工程材料有限公司 | 硅胶布|电磁炉垫片|特氟龙胶带-江苏浩天复合材料有限公司 | Jaeaiot捷易科技-英伟达AI显卡模组/GPU整机服务器供应商 | 【黄页88网】-B2B电子商务平台,b2b平台免费发布信息网 | 吸污车_吸粪车_抽粪车_电动三轮吸粪车_真空吸污车_高压清洗吸污车-远大汽车制造有限公司 | SMC-SMC电磁阀-日本SMC气缸-SMC气动元件展示网 | 艾乐贝拉细胞研究中心 | 国家组织工程种子细胞库华南分库 | 西宁装修_西宁装修公司-西宁业之峰装饰-青海业之峰墅级装饰设计公司【官网】 | 合肥通道闸-安徽车牌识别-人脸识别系统厂家-安徽熵控智能技术有限公司 | 识禅_对禅的了解,从这里开始 | 珠宝展柜-玻璃精品展柜-首饰珠宝展示柜定制-鸿钛展柜厂家 | 连续油炸机,全自动油炸机,花生米油炸机-烟台茂源食品机械制造有限公司 | 塑胶地板-商用PVC地板-pvc地板革-安耐宝pvc塑胶地板厂家 | 深圳快餐店设计-餐饮设计公司-餐饮空间品牌全案设计-深圳市勤蜂装饰工程 | 中国品牌排名投票_十大品牌榜单_中国著名品牌【中国品牌榜】 | 铁艺,仿竹,竹节,护栏,围栏,篱笆,栅栏,栏杆,护栏网,网围栏,厂家 - 河北稳重金属丝网制品有限公司 山东太阳能路灯厂家-庭院灯生产厂家-济南晟启灯饰有限公司 | 头条搜索极速版下载安装免费新版,头条搜索极速版邀请码怎么填写? - 欧远全 | 红立方品牌应急包/急救包加盟,小成本好项目代理_应急/消防/户外用品加盟_应急好项目加盟_新奇特项目招商 - 中红方宁(北京) 供应链有限公司 | 凝胶成像仪,化学发光凝胶成像系统,凝胶成像分析系统-上海培清科技有限公司 |