無秩序配列の中央値
8505 ワード
無秩序配列の中央値
ソートアルゴリズムは使用できず,時間的複雑度O(n)が要求される.
転載先:https://www.cnblogs.com/George1994/p/10749180.html
ソートアルゴリズムは使用できず,時間的複雑度O(n)が要求される.
# -*- coding: utf-8 -*-
# @Time : 2019/4/22 10:42 AM
# @Author : George
# @File : main7.py
# @Contact : [email protected]
def heapify(seq, start, end):
"""
start end ,
:param seq:
:param start:
:param end:
:return:
"""
# start
left, right = 2 * start + 1, 2 * (start + 1)
mi = start
#
if left < end and seq[mi] > seq[left]:
mi = left
if right < end and seq[mi] > seq[right]:
mi = right
if mi != start:
#
seq[start], seq[mi] = seq[mi], seq[start]
heapify(seq, mi, end)
def find_mid_num(nums):
heap_num = len(nums)//2
heap = nums[:heap_num+1]
#
start, end = len(heap) // 2 - 1, len(heap)
for i in range(len(heap)//2-1, -1, -1): # n/2
heapify(heap, i, end)
# ,
# ,
for j in range(heap_num + 1, len(nums)):
if nums[j] > heap[0]:
#
print ' %s %s' % (heap[0], nums[j])
heap[0] = nums[j]
heapify(heap, 0, end)
# ,
return heap[0] if len(nums) % 2 else (heap[0] + min(heap[1], heap[2])) / 2.0
転載先:https://www.cnblogs.com/George1994/p/10749180.html