一、问题描述
1、求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低
2、例如:
lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5
lists = [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 2
11 3
11 4 1
11 111 12 22
2,streaming程序如下:
vim sorted.sh
#!/bin/bash export 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 22
11 3
11 2
11 4 1
11 1
以上这篇python 实现在无序数组中找到中位数方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持。
python,无序数组,中位数
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新日志
- 小骆驼-《草原狼2(蓝光CD)》[原抓WAV+CUE]
- 群星《欢迎来到我身边 电影原声专辑》[320K/MP3][105.02MB]
- 群星《欢迎来到我身边 电影原声专辑》[FLAC/分轨][480.9MB]
- 雷婷《梦里蓝天HQⅡ》 2023头版限量编号低速原抓[WAV+CUE][463M]
- 群星《2024好听新歌42》AI调整音效【WAV分轨】
- 王思雨-《思念陪着鸿雁飞》WAV
- 王思雨《喜马拉雅HQ》头版限量编号[WAV+CUE]
- 李健《无时无刻》[WAV+CUE][590M]
- 陈奕迅《酝酿》[WAV分轨][502M]
- 卓依婷《化蝶》2CD[WAV+CUE][1.1G]
- 群星《吉他王(黑胶CD)》[WAV+CUE]
- 齐秦《穿乐(穿越)》[WAV+CUE]
- 发烧珍品《数位CD音响测试-动向效果(九)》【WAV+CUE】
- 邝美云《邝美云精装歌集》[DSF][1.6G]
- 吕方《爱一回伤一回》[WAV+CUE][454M]