2016 年第 43 题

题目描述

给定 n 个正整数构成的集合 A = {a1, a2, ..., an}，将其划分为两个不相交子集 A1 和 A2，要求：

1. |n1 - n2| 最小，其中 n1、n2 分别是两个子集的元素个数。
2. |S1 - S2| 最大，其中 S1、S2 分别是两个子集元素和。

请给出高效算法。

解题思路

要让元素个数差最小，两个子集的大小必须尽量接近：

• 若 n 为偶数，两个子集各 n / 2 个。
• 若 n 为奇数，两个子集分别取 n // 2 和 n // 2 + 1 个。

要让和的差尽量大，就应该让较小的一半元素放入一个集合，较大的一半元素放入另一个集合。

因此本质就是：

1. 找到数组中间位置。
2. 按中位数做一次划分。
3. 前半部分作为 A1，后半部分作为 A2。

可以直接排序实现，也可以用快速选择只做中位划分。为了代码清晰，下面给出排序版。

手算示例

A = [5, 2, 8, 1, 9, 4]

排序后：
[1, 2, 4, 5, 8, 9]

前半部分 A1 = [1, 2, 4]，S1 = 7
后半部分 A2 = [5, 8, 9]，S2 = 22

|n1 - n2| = 0，为最小
|S1 - S2| = 15，为最大

Python 实现

def split_set(nums):
    if not nums:
        return [], [], 0

    nums = sorted(nums)
    mid = len(nums) // 2

    a1 = nums[:mid]
    a2 = nums[mid:]
    diff = abs(sum(a2) - sum(a1))

    return a1, a2, diff

复杂度分析

• 时间复杂度：O(n log n)；若用快速选择可降到期望 O(n)
• 空间复杂度：O(n)；若原地划分可进一步优化

易错点

• 先满足“元素个数差最小”，再谈“和差最大”。
• 正确划分后，一定是“小的一半”和“大的一半”分开。
• 如果题目要求原地划分，排序代码虽然好理解，但不是最优实现。

对应题

未找到高度一致的公开原题。问题模型基于快速排序 / 选择算法中的 partition 思想。

难度

⭐️⭐️⭐️