# LeetCode Easy 561. Array Partition I

tags: leetcode

問題

• Explore
• Problems

アイデア

｢2n個($n \in \mathbb{N}$)の整数の配列が与えられた時に，n個のペアを作り，それぞれのペアの小さい方の和を最大にせよ｣という問題です．

最小なものは絶対にこの和に加わるということに気付くと解くことが出来ます

解法

• 配列の中でもっとも小さい要素は他のどんな数とペアになっても和に加わります．
  • そのため，ペアとなるのは残りの要素のうち最小の要素となると和が大きくなります
• これを再帰的に考えると最も小さい要素，3番目に小さい要素…と加えると良いです
• 配列をソートして2つずつ要素を取り出します．

計算量

要素の個数を$N$とします．

• 時間計算量
  • $O(N \log N)$
• 空間計算量
  • $O(1)$

Python

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