小编Sub*_*sis的帖子

给定一个由 n 个整数组成的数组，我们如何有效地重新排列其中的数字，使得对于任意两个数字 a[i] 和 a[j] (i < j)，它们的平均值不在两个元素之间？
请注意 (i + 2) <= j < n 其中 n 是数组的长度。数字和平均值只允许使用正整数，即对于 1 和 2，平均值是 1.5，我们需要忽略它。原始数组中的数字是不同的。

让我们举个例子 - 如果给定的数组是 arr = [1, 2, 4, 7]，这不是当前状态下的有效排列，因为 arr[0] 和 arr[3] 的平均值是 4，其中 arr [2]，所以平均 4 位于 1 和 7 之间。但是 [1, 2, 7, 4] 是一个有效的排列。

我想了想，这是我能想出的解决方案，我找不到算法优化的真正范围。我遇到了一些解决方案，例如根据偶数/奇数索引递归地对数组进行分区并将它们合并回来，但它对某些输入不起作用。

from copy import copy
from collections import defaultdict

def arrange_numbers_no_avg_in_between(arr):

    def permutations_helper(i):
        if i == len(arr) - 1:
            num_index_mapping = defaultdict(list)
            for idx, num in enumerate(arr):
                num_index_mapping[float(num)].append(idx)
                
            for …