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

一、问题描述

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 实现在无序数组中找到中位数方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Python寻找两个有序数组的中位数实例详解

    Python寻找两个有序数组的中位数 审题: 1.找出意味着这是一个查找算法题 2.算法复杂度log级别,就是提示你是二分查找 3.二分查找实现一般为递归 (1)递归包括递归体  (2)终止条件 思路: 定理: 1.有序数组中有一半的元素小于等于数组的中位数,有一半的元素大于等于中位数(如果数组中元素个数是奇数,那么这里的一半并不是严格意义的1/2) 2.如果我们去掉其中一个数组比中位数小的k个数,再去掉另一个数组中比中位数大的k个数,得到的合并子数组的中位数和原来的中位数相同. eg:[1,2

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

    一.问题描述 1.求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置.要求:不能使用排序,时间复杂度尽量低 2.例如: lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5 lists = [3, 1, 2] , 中位数为 2 3.算法思想: 利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数

  • Python实现在某个数组中查找一个值的算法示例

    第一种算法思路: 第一步:随机出来一个数组的下标 第二步:判断下标对应的值是否等于被查找的值,是的话终止,已找到,否的话转第三步. 第三步:判断是否随机完数组的所有下标,是的话终止,没找到,否的话转第一步. 代码如下: #本程序的功能是在字典中查找存在某个值 import random di = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6} key = 2 di1 = {} while True: tmp = random.choice(di.keys()) #随机

  • python获取元素在数组中索引号的方法

    本文实例讲述了python获取元素在数组中索引号的方法.分享给大家供大家参考.具体如下: 这里python是通过index方法获取索引号的 li = ['a', 'b', 'new', 'D', 'z', 'example', 'new', 'two', 'elements'] print li.index("example") print li.index("new") print li.index("z") print "c&quo

  • C++算法之在无序数组中选择第k小个数的实现方法

    本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in

  • Python实现找出数组中第2大数字的方法示例

    本文实例讲述了Python实现找出数组中第2大数字的方法.分享给大家供大家参考,具体如下: 题目比较简单直接看实现即可,具体的注释在代码中都有: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:找出数组中第2大的数字 ''' def find_Second_large_num(num_list): ''''' 找出数组中第2大的数字 ''' #直接排序,输出倒数第二个数即可 tmp_list=sorted(num_lis

  • Python实现删除排序数组中重复项的两种方法示例

    本文实例讲述了Python实现删除排序数组中重复项的两种方法.分享给大家供大家参考,具体如下: 对于给定的有序数组nums,移除数组中存在的重复数字,确保每个数字只出现一次并返回新数组的长度 注意:不能为新数组申请额外的空间,只允许申请O(1)的额外空间修改输入数组 Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1

  • 用python一行代码得到数组中某个元素的个数方法

    想法由来 今天写代码过程中遇到一个需求,计算一个list中数值为1的元素的个数,其中这个list的元素数值不是为0就是为1. 一开始想到的是写个方法来计算: # 返回一个0,1数组中1的数量 def num_one(source_array): count = 0 for x in source_array: if x == 1: count += 1 return count 嗯好吧,然后觉得这是最low的方法了,就在想强大的python可不可以一行代码就做到以上的效果,然后发现真的可以. c

  • python [:3] 实现提取数组中的数

    搜索答案搜索不到,自己试了一把. 首先生成一维数组 a =np.array([1,2,3,4,5,6,7,8,9]) >>> print a [1 2 3 4 5 6 7 8 9] 取数组前3个值 b =a[:3] >>> print b [1 2 3] 取前3个以后的值 b =a[3:] >>> print b [4 5 6 7 8 9] 取数组的后3个值 b =a[-3:] >>> print b [7 8 9] 取数组后3个以前

  • Python实现从N个数中找到最大的K个数

    提出问题: 如何在某集合里面找出最大或最小的K个元素. 解决思路: 找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个. 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq.nlargest(4,nums)) #-->最大的4个 print(heapq.nsmallest(4,nums)) #-->最小的4个

  •  javascript数组中的findIndex方法 

    目录 1findIndex()简单介绍 2编辑器 3代码部分 4运行结果 5总结 1findIndex()简单介绍 findIndex() 方法返回传入一个测试条件(函数)符合条件的数组第一个元素位置. 当数组中的元素在测试条件时返回 true 时, findIndex() 返回符合条件的元素的索引位置(注:find()返回的是元素),之后的值不会再调用执行函数.如果没有符合条件的元素返回 -1(注:find()返回的是undefined). findIndex()与find()的使用方法相同,

随机推荐