将整数数组分为K组，使得每组具有最小范围

Question

因此，更正式地说，我获得了N个数字，并需要将它们分成K组，使得这些组中的任何一个都不为空。每个组中范围的总和需要是最小的。例如：

N = 4，K = 2，输入为 {5,3,1,1}。

一种可能的解决方法是{5,3}，{1,1}。范围的总和为2 ((5-3)+(1-1))。

还有一种看待问题的方式是{1,1,3}{5}，也是2 ((3-1)+(单个数字的范围为0))。

范围始终是组中最大数字和最小数字之间的差异。

当我在搜索互联网时，很明显我需要使用动态规划，但我能想到的所有解决方案都是针对K = 2的。

有人可以提供帮助吗？

- chen20032

---

这些组需要包含连续的数字吗？@Koekje 需要将其分成 k 组，并且有 N 个数字，其中 k<N。 - Gijs Den Hollander

Answer 1

1. 对数组进行排序。
2. 令a_m为数组中的第m个元素；然后，让a_m = a_m – a_m–1 ∀m ∈ [1; N)。减法循环必须向后运行，以避免改变a_m–1。a₀ ≡ 0。
3. 对结果数组进行排序，保持元素的初始索引与元素本身按相同顺序排序。
4. 取最后的K-1个索引：这些，加上0，是所要查找的分组的第一个元素的索引。

- hidefromkgb

---

如果数组已经排序，并且K很小，您将获得O(n * log(n))的复杂度，但是通过在减法后找到前K-1个最佳索引而不进行排序，您可以获得O(n)的复杂度。 - gdelab

即使排序是不可避免的，O(n)的时间复杂度仍然可以保持不变。例如，这是我的实现 的原地MSR基数排序。如果所有数组元素的大小都与n无关（例如32位），则此算法是严格线性的。 - hidefromkgb

Answer 2

通过动态规划，您已经为k = 2提出了一个解决方案。现在考虑如何将其扩展到k = 3。

假设f2(n)返回k = 2和前n个数字的最佳解决方案，则f3(n) = f2(n-m) + err(n-m, n)。这是一种扩展方法。

- ElKamina

Answer 3

假设您的数据已经排序，您可以在线性时间内完成。

您可以将数据视为介于min_value和max_value之间的轴上。显然，聪明的解决方案不使用非连续的组，因此任何聪明的解决方案都可以表示为您的轴上的K个段的组合，每个段[x1，x2]表示您的数据中所有位于x1和x2之间的数字。

您的解决方案的总成本是所有段长度的总和，这也是max_value-min_value-(所有段之间的空间)。您的段之间的空间本身由K-1个“空段”组成，即其中没有输入数字的段，即两个连续输入数字之间的段。您想要的是最大化K-1个这样段的长度之和。

所以，您只需要执行以下操作（简单版本）：

• 如果需要，对输入进行排序
• 对于所有i，计算B[i] = A[i+1] - A[i]（其中A是已排序的输入数组）
• 检索B的前K-1个最大值（仍然是线性时间，实际上可以与前一步同时完成）
• 这些是您的组的边界，因此您可以再次遍历A以制作组本身（现在您有了边界）（此步骤也可以与前面的步骤一起完成）

如果不同值的数量大于K，则必须非空地分组。否则，您可以轻松地拆分包含相同值的重复项以使所有组都非空。

复杂度（如果已排序）：O(n*k)（最多），如果K是常数，则为O(n)。如果不是，则只需改进搜索最佳的K-1个段即可获得最多O(n log(n))

如所述，额外的内存复杂度很容易达到O(K)

- gdelab

Answer 4

所以在这个问题中，我们想要最小化组的范围。

假设我们有数组A = {1,3,5,7,5,2}

每个数组的最大范围是max[a]-min[a]，最小范围为0

我们可以使用二分搜索的变体来找到最小范围，这个答案是在组必须包含连续数字的约束下得出的。

对于二分搜索，我们需要选择边界，这些边界由数组的最小和最大范围给出。

这个伪代码/Java代码看起来像这样。

main(){
  int upper = max(A)-min(A); 
  int lower = 0;  


  while (true) {
    int mid =  upper-lower;  
    int blocks = calculateBlockCount(A, mid); 
    if (blocks < K) {
      upper = mid - 1;
    } 
    else if (blocks > K) {
      lower = mid + 1;
    } 
    else {
      return upper;
      break;
    }
  }
 }

    private static int calculateBlockCount(int[] array, int range) {
      int count = 0;
      int[] dumie_array;
      int dumie_array[].add[array[0]];

      for (int i = 0; i < array.length; i++) {
        int dumie_array[].add[array[i]]
         if (Func_range(dumie_array) > range) {
           count++;
           dumie_array = array[i];
         } 
         else {
           dumie_array.add(array[i]);
         }
      }
      return count;
    }

    private static int Func_range(int[] input) {
       int range = 0;
       range= max(input)-min(input)
       return sum;
     }

希望仍有所帮助

我认为大部分内容都适用于Java，只有C++中的添加功能不可用。（不想通过创建ArrayList来写那么多代码。）但我认为程序的思路应该是清晰的。
这一切都基于这篇文章 需要解释搜索最小大和算法。 这是一个非常相似的问题。

祝好， Gijs

- Gijs Den Hollander