Zenn
🖋

LeetCode 561. Array Partition

に公開
Go
LeetCode
tech

はじめに

LeetCode 「561. Array Partition」の問題をGoで解きました。

問題

https://leetcode.com/problems/array-partition/description

問題文

Given an integer array nums of 2n integers, group these integers into n pairs (a1, b1), (a2, b2), ..., (an, bn) such that the sum of min(ai, bi) for all i is maximized. Return the maximized sum.

和訳
2n個の整数からなる整数配列numsが与えられた場合、これらの整数をn組のペア(a1, b1), (a2, b2), ..., (an, bn)にグループ化し、すべてのiについてmin(ai, bi)の合計が最大になるようにします。最大化された合計を返します。

例

Input: nums = [1,4,3,2]
Output: 4
Explanation: All possible pairings (ignoring the ordering of elements) are:
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
So the maximum possible sum is 4.

Input: nums = [6,2,6,5,1,2]
Output: 9
Explanation: The optimal pairing is (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9.

制約

  • 1 <= n <= 104
  • nums.length == 2 * n
  • -104 <= nums[i] <= 104

解答1

与えられた配列からペアを作り、ペアのうち小さい数を合計して最大化させる問題です。
配列からあらゆるパターンのペアを作るのでは非効率なため、効率的に解決できないか考えます。

この問題では、ペアごとの小さい方の値を合計していくため、ペア内の小さい方の値ができるだけ大きいとよいです。
そのため、配列を昇順にソートし、隣り合う要素を順番にペアにすれば、小さい方の値をなるべく大きくできます。
このとき、常に先頭側（偶数番目のインデックス）を選んで足せばよいため、i += 2で回すことで解けます。

コード

func arrayPairSum(nums []int) int {
	sum := 0
	slices.Sort(nums)

	for i := 0; i < len(nums); i += 2 {
		sum += nums[i]
	}

	return sum
}

計算量

  • 時間計算量：O(n log n)
    • 配列のソートにO(n log n)、その後のループはO(n)であるため、全体としてはO(n log n)
  • 空間計算量：O(1)（※ソートがin-placeで行われる前提）
GitHubで編集を提案

Discussion