[leetcode] Array Partition I

Array Partition I

に答える

[1,4,3,2]がある場合、[1,2/3,4]に並べ替えられます.ここで1+3を作ると一番値打ちがあります別の例では[6,2,6,5,1,2]で並べ替えられた[1,2/2,5/6,6]で1+2+6を行えばよい.
この解法の並べ替えの最大時間複雑度はO(N)であった.

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums = sorted(nums)
        sum = 0
        for index in range(0, len(nums), 2):
            sum += nums[index]
        return sum

最初に思いついた方法

最低価格から最低価格まで計算して、いろいろ考えました.

参考資料

Nick White