数组拆分

🎯 问题描述（来源于LeetCode）

描述：
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。
返回该 最大总和 。
说明：

  • 1 <= n <= 104

  • nums.length == 2 * n

  • -104 <= nums[i] <= 104
    示例：

  • 示例 1：

1
2
3
4
5
6
7
输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4
  • 示例 2：
1
2
3
输入：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：基数排序

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        offed=10000
        nums=[num+offed for num in nums ]
        size=len(str(max(nums)))
        for i in range(size):
            buckets=[[]for _ in range(10)]
            for num in nums:
                buckets[num//(10**i)%10].append(num)
            nums.clear()
            for bucket in buckets:
                for num in bucket:
                    nums.append(num)
        n = len(nums)
        sum=0
        for i in range(n):
            nums[i]-=10000
            if i&1==0:
                sum+=nums[i]
        return sum

思路1：📊 性能分析

提交结果
  • 运行时间：95ms击败6.00%
  • 内存消耗：22.32MB击败5.09%
复杂度验证
  • 时间复杂度：O(NLogN)O(NLogN)
  • 空间复杂度：O(N)O(N)

思考