列表中的中间值

Question

我需要一个向量来存储主列表"v“的中间值的中值。我用下面的代码尝试了一些东西，但我只能以正确的方式编写一些值。

v=[1,2,3,4,5,6,7,8,9,10]
final=[]
nfac=0
for j in range (0,4):
    nfac=j+1
    for k in range (0,nfac):
        if k%2==0:
            final.append(v[10/2**(nfac)-1])
        else:
            final.append(v[9-10/2**(nfac)])

v=1,2,3,4,5,6,7,8,9,10的第一个中位数是5

然后，我想要剩下的中介分别列出1,2,3,4和6,7,8,9,10，即2和8。诸若此类。

“最终”名单必须以下列形式列出：

final=5,2,8,1,3,6,9,4,7,10

Answer 1

请注意，您定义的任务基本上等同于从数组构造二进制堆。

首先，一定要定义一个帮助函数来查找中间值：

def split_by_median(l):
    median_ind = (len(l)-1) // 2
    median = l[median_ind]
    left = l[:median_ind]
    right = l[median_ind+1:] if len(l) > 1 else []
    return median, left, right

按照您所给出的示例，您希望以广度优先的方式处理结果子列表，因此我们需要一个队列来记住以下任务：

from collections import deque   
def construct_heap(v):
    lists_to_process = deque([sorted(v)])
    nodes = []
    while lists_to_process:
        head = lists_to_process.popleft()
        if len(head) == 0:
            continue

        median, left, right = split_by_median(head)
        nodes.append(median)
        lists_to_process.append(left)
        lists_to_process.append(right)

    return nodes

因此，最后调用该函数：

print(construct_heap([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])) #  [5, 2, 8, 1, 3, 6, 9, 4, 7, 10]
print(construct_heap([5, 1, 2])) #  [2, 1, 5]
print(construct_heap([1, 0, 0.5, -1])) #  [0, -1, 0.5, 1] 
print(construct_heap([])) #  []