av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

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

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

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

一、問題描述

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

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ù)尋找中位

平均時間復(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)

知識補充: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)文章:
主站蜘蛛池模板: 国产精品久久久久久久久久久久冷 | 午夜影院毛片 | 成人教育av | 一本大道久久a久久精二百 欧洲一区二区三区 | 成人精品国产一区二区4080 | 国产视频一区在线 | 日韩欧美中文字幕在线观看 | 午夜寂寞影院在线观看 | 黄色av网站在线免费观看 | 成人av一区二区三区 | 国产高清在线 | 91成人小视频 | 91成人免费 | 亚洲精品一区中文字幕乱码 | 美女中文字幕视频 | 久久久综合久久 | h在线看| 欧美电影大全 | 欧美激情亚洲激情 | 一区二区三区视频 | 国产精品一区二区三区久久 | 亚洲永久免费观看 | 亚洲码欧美码一区二区三区 | 天堂网中文 | 国产亚洲精品精品国产亚洲综合 | 久久久久国产精品 | 久久久国 | 少妇黄色 | 日韩中文字幕2019 | 日韩成人免费视频 | 久久国产精品无码网站 | 国产精品久久久av | 青青草精品 | 午夜天堂 | 伊人激情网 | 日本不卡视频 | 久久国| 亚洲欧美国产精品久久 | 国产精品99久久久久久宅男 | 亚洲国产成人av好男人在线观看 | 欧美一区二区在线免费观看 |