溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一、問題描述
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 實現在無序數組中找到中位數方法就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
