脚本专栏

python 实现在无序数组中找到中位数方法
脚本专栏 2024/11/8 佚名
3 2

一、问题描述

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 1

11 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
白云城资源网 Copyright www.dyhadc.com
www.dyhadc.com 白云城资源网
129,905影音资源
244,626技术资源
111,817软件资源
578,645站长资源

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网 更多链接
白云城资源网 Copyright www.dyhadc.com