LeetCode 561. Array Partition能否以O(n)时间复杂度求解？

问题描述 #

给定一个包含2n个整数的数组nums，需将其分成n对(a₁,b₁)、(a₂,b₂)、…、(aₙ,bₙ)，使所有min(aᵢ,bᵢ)的和最大化，返回该最大和。

示例1： #

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的配对（忽略元素顺序）：

• (1,4)、(2,3) → min(1,4) + min(2,3) = 1+2=3
• (1,3)、(2,4) → min(1,3) + min(2,4) =1+2=3
• (1,2)、(3,4) → min(1,2)+min(3,4)=1+3=4
  最大和为4。

示例2： #

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优配对为(2,1)、(2,5)、(6,6)，min(2,1)+min(2,5)+min(6,6)=1+2+6=9。

约束条件： #

• 1 ≤ n ≤ 10⁴
• nums.length == 2*n
• -10⁴ ≤ nums[i] ≤ 10⁴

现有O(nlogn)解法 #

当前已有基于排序的解法，时间复杂度为O(nlogn)：

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        for i in range(0, len(nums), 2):
            ans += nums[i]
        return ans

问题问询 #

请问该问题是否可以以O(n)时间复杂度求解？

解答 #

可以，利用计数排序就能实现O(n)时间复杂度的解法。因为题目限定了数组元素的取值范围是[-10⁴, 10⁴]，总共有20001个可能的数值，这个范围固定且有限，完全符合计数排序的适用场景。

具体思路 #

1. 偏移处理负数：因为元素可能为负，我们将所有数值偏移10000，把-10⁴映射到索引0，10⁴映射到索引20000，这样可以用一个长度为20001的数组来统计每个数值的出现次数。
2. 遍历计数数组计算总和：按从小到大的顺序遍历计数数组，同时维护一个“未配对计数”变量：
   • 当遇到一个数值出现k次时，结合当前未配对的数量，计算能形成多少对，每一对中较小的数值（就是当前遍历到的这个数）会被加入总和。
   • 处理完当前数值后，更新未配对计数，用于和下一个数值配对。

O(n)时间复杂度的代码实现 #

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        offset = 10000
        count = [0] * (20001)
        # 统计每个数字出现的次数
        for num in nums:
            count[num + offset] += 1
        
        res = 0
        unpaired = 0  # 记录未配对的元素数量
        for i in range(20001):
            if count[i] == 0:
                continue
            # 当前数字的实际值
            num = i - offset
            # 计算当前能形成的配对数
            total = count[i] + unpaired
            pairs = total // 2
            res += pairs * num
            # 更新未配对的数量
            unpaired = total % 2
        return res

这个解法的时间复杂度是O(n + M)，其中M是数值范围的大小（这里M=20001，是常数），所以整体时间复杂度为O(n)。

内容的提问来源于stack exchange，提问作者code_omelette