如何在O(n)时间内将带键与权重的数组分为满足条件的两个子数组？

前提条件 #

首先计算数组所有元素的总权重total_weight：

• 若total_weight为奇数，直接返回无解（无法分成权重相等的两组）
• 目标权重target = total_weight / 2

核心思路 #

利用BFPRT算法（最坏O(n)时间的选择算法），结合权重和的计算，在每一步划分中快速缩小搜索范围，避免重复遍历数组找最大元素的O(n²)开销。

具体步骤 #

1. 数组划分与权重计算

   • 用BFPRT选择一个基准元素pivot（保证每次划分至少排除3/10的元素，维持线性时间复杂度）
   • 将数组划分为三个子集：
     • L：所有键小于pivot.key的元素
     • M：所有键等于pivot.key的元素
     • R：所有键大于pivot.key的元素
   • 计算sum_L（L的总权重）、sum_M（M的总权重）

2. 分支处理

   • 情况1：sum_L == target
     直接将L作为组1，M ∪ R作为组2。满足组1所有键 < pivot.key ≤ 组2所有键，且权重相等。
   • 情况2：sum_L < target < sum_L + sum_M
     返回无解。因为相同键的元素无法跨组拆分（否则组1和组2会存在相同键，违反“组1所有键小于组2所有键”的要求），无法凑出目标权重。
   • 情况3：sum_L + sum_M ≤ target
     目标权重剩余target - (sum_L + sum_M)，递归处理子集R（此时L ∪ M全部归入组1，只需在R中找剩余权重的分割）。
   • 情况4：sum_L > target
     递归处理子集L，目标权重仍为target（需在L中找到满足权重的分割）。

时间复杂度分析 #

BFPRT的划分步骤是O(n)，且每次递归处理的数组规模最多为7n/10，根据主定理：
T(n) = T(7n/10) + O(n)
解得最坏时间复杂度为O(n)，完全符合要求。

关键优化点 #

• 放弃每次调整分组时查找最大键的操作，改为通过BFPRT的线性划分，在每一步同时计算权重和，一次性缩小搜索范围。
• 利用BFPRT的最坏O(n)选择特性，避免了普通Quick Select的最坏O(n²)风险。

内容的提问来源于stack exchange，提问作者Nati Shen-Gordon