来源:Google面试问题
编写例程以确保输入中的相同元素在输出中最大程度地分布？
基本上,我们需要以这样的方式放置相同的元素,使得TOTAL扩展尽可能最大.
例:
Input: {1,1,2,3,2,3}
Possible Output: {1,2,3,1,2,3}
Total dispersion = Difference between position of 1's + 2's + 3's = 4-1 + 5-2 + 6-3 = 9 .
我不是在所有 肯定的是,如果有可用的this.Also最佳多项式时间算法,没有其他细节提供了除此之外的其他问题.
我的想法是,计算输入中每个元素的频率,然后将它们一次排列在输出中,每个不同的元素,直到所有频率都耗尽.
我不确定我的做法.
任何方法/想法的人.
itertools.combinationsin python 是一个强大的工具，用于查找r项的所有组合，但是，我想知道它的计算复杂度。
假设我想知道n和r方面的复杂性，当然它会给我n项列表中的所有r项组合。
根据官方文档，这是粗略的实现。
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for …