排列数组，使相邻的空间较小，从而给出最小的总和

Question

我有一个大小均匀的数字数组，这是我的任务：

a) 丢弃数组中的任意 2 个元素。b) 然后将元素配对并计算该对中元素之间的差值之和，使之和最小。

例子：

array size even say 8.
array elements : 1,3,4,6,3,4,100,200

Ans:
5

解释：

在这里，我将删除 100 和 200，因为将它们配对后，差值为 (200 - 100) = 100。因此剩余元素为 [1,3,4,6,3,4] 具有最小总和的对为：(1 3 ) , (4 3), (6 4)。=|3-1| = 2, |4-3|=1,|6-4| = 2. 所以总和 = 2 + 1 + 2 = 5

例子：

array size even say 4.
array elements : 1,50,51,60

Ans:
1

解释：这里我将删除 1 和 60，这样我将得到最小的总和。所以剩下的元素是 [50, 51]，与相邻的 [50 51] = 1 相同。在这种情况下，我的代码将失败并返回 49。

在java中如何实现这一点呢？

我尝试像这样对元素进行排序，但这并不是适用于所有类型输入的正确方法。

public static int process(int[] a) {
   int n = a.length;
   int n1 = n/2-1;
   Arrays.sort(arr);
   int sum = 0;
   for(int i=0; i<n1*2; i+=2) {
     sum += a[i+1] - a[i];
   }
   return sum;
}

Answer 1

在这类问题中，真正的问题是找到一个好的算法。
这篇文章将坚持这一方面。最后提供了 C++ 代码只是为了说明它。

很明显，我们必须从对数组进行排序开始。
解决方案包括迭代计算三个总和，其中

sum0 is the minimum sum assuming no element has been removed
sum1 is the minimum sum assuming one element has been removed
sum2 is the minimum sum assuming two elements has been removed

在此过程中，代码必须跟踪可用于计算差值的最后一个元素，每个和 ( i_dispo0, i_dispo1, i_dispo2) 对应一个元素。

原则：

- if sum1 > sum0: sum1 is replaced by sum0
- if sum2 > sum1: sum2 is replaced by sum1

复杂度： O(n logn)用于排序，O(n)用于优化阶段。

代码：

该算法通过以下简单的 C++ 代码进行说明。
应该很容易理解。

输出： 5 1 2 0 2

sum0 is the minimum sum assuming no element has been removed
sum1 is the minimum sum assuming one element has been removed
sum2 is the minimum sum assuming two elements has been removed