将给定的数组拆分为k个子数组,使所有子数组的最大和最小

  • 本文关键字:数组 拆分 python arrays
  • 更新时间 :
  • 英文 :


我正在努力解决上面的问题,我有一个数组,例如[1,2,4,5],我想把它分成k个子数组,这样这些子数组的最大大小就是可能的最小值例如,对于k=3,这将是:

[5] [4,1] [3,2] 
max(...) = 5

我能找到的唯一类似的东西是:https://www.geeksforgeeks.org/split-the-given-array-into-k-sub-arrays-such-that-maximum-sum-of-all-sub-arrays-is-minimum/

但是,对于上面的例子,它没有给出正确的结果,也没有返回数组,这是我的情况所需要的。

理想情况下,我想在Python中做到这一点,但伪代码也可以在中工作

非常感谢您对此的任何帮助

如果您有一个长度为L的数组,并且需要分离成k子集,则最终会得到长度为L'=int(L/k(和长度为L'=L%k=(L-L%k(/k子数组。如果对数组x = np.sort(x)进行排序,则长度为l'的子数组将是具有x的最右边元素和l’-1最左边元素的子数组。其他n数组以类似的方式构建,总是将最右边的元素与L'-1最左边的元素组合在一起。

我认为这应该给出正确的答案,因为最右边的元素总是最大的,最小的组合总是与数组中最左边的元素在一起。任何其他组合都相等或更大。

在您的示例中,数组已经排序,它应该给出长度为l'=2l'=15n=2,这将是[4,1],然后是[3,2]

最新更新