第43题：满分15分

要求$|n1 – n2|$绝对值最小，其实就是对于n为偶数，划分成两个一样大的数组，对于n为奇数划分为两个大小相差1的数组。划分成的两个数组还要保证数组之和的差的绝对值最大，如果说差的绝对值最小的话，划分起来还有些难度，但是如果要最大的绝对值，只需要把大数都划分到同一个数组，把剩余的小数都划分到另一个数组就可以。

方法一：排序

先把数组从小到大排序，那么前$\lfloor n/2 \rfloor$个元素放到第一个数组里，后面元素放到第二个数组里即可。时间和空间复杂度取决于所用排序算法

方法二：快速选择

我们需要前$\lfloor n/2 \rfloor$小的元素，放到第一个数组中，所以可以使用快速选择得到Topk小的所有元素，但这样不能直接存到原数组中，否则空间复杂度会提高为$O(n)$。不过可以用快速排序求出原数组的中位数，再直接在原数组里划分，这样空间复杂度是$O(logn)$