python 实现在无序数组中找到中位数方法

2023-07-29 21:29:04 247

一、问题描述

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)

二、程序

classSolution(object):

deffindmedian(self,lists):
ifnotlistsorlen(lists)==0:
return[]

n=len(lists)
ifn%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)
returnmid
else:
mid=self.partition(lists,n/2,0,n-1)
returnlists[mid]

defpartition(self,lists,k,start,end):

key=lists[start]
left,right=start,end

whileleftkey:
right=right-1
lists[left]=lists[right]

whileleftk:
returnself.partition(lists,k,start,left-1)
else:
returnself.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)

知识补充：pythonstreaming实现某个字段排序

一，hadoopstreaming默认情况

1，在hadoopstreaming的默认情况下，是以\t作为分隔符的，标准输入时，每行的第一个\t之前的内容作为key，第一个\t之后的内容作为value。注意，如果一个\t字符都没有，那么整行作为key。

2，streaming的一些参数如下：

-Dstream.map.output.field.separator：设置map输出中key和value的分隔符
-Dstream.num.map.output.key.fields：设置map程序分隔符的位置，该位置之前的部分作为key，之后的部分作为value
-Dmap.output.key.field.separator:设置map输出中key内部的分割符
-Dnum.key.fields.for.partition:指定分桶时，key按照分隔符切割后，其中用于分桶key所占的列数（配合-partitionerorg.apache.hadoop.mapred.lib.KeyFieldBasedPartitioner使用）
-Dstream.reduce.output.field.separator：设置reduce输出中key和value的分隔符
-Dstream.num.reduce.output.key.fields：设置reduce程序分隔符的位置

二，pythonstreaming实现某个字段的排序

1，输入数据:catdata.txt(中间是tab键）

112
113
1141
111

111222

2，streaming程序如下：

vimsorted.sh

#!/bin/bash

exportCURRENT=/home/chunhe.liao/hadoop_streaming/sort

/usr/local/hadoop-2.6.3/bin/hadoopjar/usr/local/hadoop-2.6.3/share/hadoop/tools/lib/hadoop-streaming-2.6.3.jar\
-Dstream.map.output.field.separator='\t'\
-Dstream.num.map.output.key.fields=3\
-Dmapreduce.job.output.key.comparator.class=org.apache.hadoop.mapreduce.lib.partition.KeyFieldBasedComparator\
-Dmapreduce.partition.keycomparator.options=-k3,3nr\#按照第三列逆序排列,可以根据想要的第几段来选择。
-input"/user/test/inputdata/datas3/data.txt"\
-output"/user/test/streaming/sorted_20180711"\
-mapper"pythonmapper.py"\
-reducer"pythonreducer.py"\
-file"$CURRENT/mapper.py"\
-file"$CURRENT/reducer.py"

(2)mapper.py

#-*-coding:utf-8-*-
importsys

forlineinsys.stdin:
line=line.strip()
print('{0}'.format(line))

(3)reducer.py

#-*-coding:utf-8-*-
importsys

forlineinsys.stdin:
line=line.strip()
print("{0}".format(line))

运行命令：

bashsorted.sh

运行结果：

hdfsdfs-cat/user/test/streaming/sorted_20180711/part-00000

111222
113
112
1141
111

以上这篇python实现在无序数组中找到中位数方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持毛票票。

声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

python 实现在无序数组中找到中位数方法

热门推荐

随机推荐