python 实现在无序数组中找到中位数方法 - CSDN文库

108 浏览量更新于2023-03-16 收藏 56KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

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 实现某个字段排序实现某个字段排序

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

weixin_38590784

粉丝: 3
资源: 946

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈