没有合适的资源?快使用搜索试试~ 我知道了~
一、问题描述 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 , 那么中位数点在右侧,反之,中位数在左侧。然后进入相应
资源推荐
资源详情
资源评论
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 实现某个字段排序实现某个字段排序
资源评论
weixin_38590784
- 粉丝: 3
- 资源: 946
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功