跳至主要內容

0561. 数组拆分

ITCharge大约 3 分钟

0561. 数组拆分open in new window

  • 标签:贪心、数组、计数排序、排序
  • 难度:简单

题目链接

题目大意

描述:给定一个长度为 2×n2 \times n 的整数数组 numsnums

要求:将数组中的数拆分成 nn 对,每对数求最小值,求 nn 对数最小值的最大总和是多少。

说明

  • 1n1041 \le n \le 10^4
  • nums.length==2nnums.length == 2 * n
  • 104nums[i]104-10^4 \le nums[i] \le 10^4

示例

  • 示例 1:
输入: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:
输入: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:计数排序

因为 nums[i]nums[i] 的范围为 [104,104][-10^4, 10^4],范围不是很大,所以我们可以使用计数排序算法先将数组 numsnums 进行排序。

要想每对数最小值的总和最大,就得使每对数的最小值尽可能大。只有让较大的数与较大的数一起组合,较小的数与较小的数一起结合,才能才能使总和最大。所以,排序完之后将相邻两个元素的最小值进行相加,即得到结果。

思路 1:代码

class Solution:
    def countingSort(self, nums: [int]) -> [int]:
        # 计算待排序数组中最大值元素 nums_max 和最小值元素 nums_min
        nums_min, nums_max = min(nums), max(nums)
        # 定义计数数组 counts,大小为 最大值元素 - 最小值元素 + 1
        size = nums_max - nums_min + 1
        counts = [0 for _ in range(size)]
        
        # 统计值为 num 的元素出现的次数
        for num in nums:
            counts[num - nums_min] += 1
        
        # 生成累积计数数组
        for i in range(1, size):
            counts[i] += counts[i - 1]

        # 反向填充目标数组
        res = [0 for _ in range(len(nums))]
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            # 根据累积计数数组,将 num 放在数组对应位置
            res[counts[num - nums_min] - 1] = num
            # 将 num 的对应放置位置减 1,从而得到下个元素 num 的放置位置
            counts[nums[i] - nums_min] -= 1

        return res

    def arrayPairSum(self, nums: List[int]) -> int:
        nums = self.countingSort(nums)
        return sum(nums[::2])

思路 1:复杂度分析

  • 时间复杂度O(n+k)O(n + k),其中 kk 代表数组 numsnums 的值域。
  • 空间复杂度O(k)O(k)

思路 2:排序

要想每对数最小值的总和最大,就得使每对数的最小值尽可能大。只有让较大的数与较大的数一起组合,较小的数与较小的数一起结合,才能才能使总和最大。

  1. numsnums 进行排序。
  2. 将相邻两个元素的最小值进行相加,即得到结果。

思路 1:代码

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum(nums[::2])

思路 1:复杂度分析

  • 时间复杂度O(n×logn)O(n \times \log n)
  • 空间复杂度O(1)O(1)