返回最大化其（平均值 - 中位数）的整数子集

Question

一组整数作为输入给出。您必须返回该集合的子集，以便该子集的均值 - 中位数是最大值。

示例 1

输入

{1,2,3,4} 

输出

{1,2,4}

示例 2

输入

{1,2,2,3,3}

输出

{2,2,3}

Answer 1

对于每个可能的中位数：

lllllmrrrrr

对 L 和 R 两个部分进行排序，然后开始从两个部分中成对选择lr最大元素，并添加每个下一个元素重新计算平均值，存储具有最佳差异的排列。对于最小元素也是如此。

有大约N可能的中位数，排序需要O(N*lgN)，在每次迭代中您需要计算平均值N，您可以在 中完成O(N)。因此，总体复杂度为O(N^3*LgN)，但很可能您可以避免在每次迭代时进行排序，而是仅对整个数组进行一次排序并在O(1)每次迭代时更新部分。有了这样的改进，确实如此O(N^2)。