【leetcode 561】配列分割I java問題解
2266 ワード
【leetcode分類下のすべての問題解は著者本人が比較して選んだ問題解であり、読みやすく、メンテナンス性に優れている.問題ごとに1つの答えしかないため、煩雑で実用的でない案を避けることができるので、必ずしも最適解とは限らない】
長さ2 nの配列を指定すると、これらの数をn対に分けることができます.例えば、(a 1,b 1)、(a 2,b 2)、...,(an,bn)、1からnまでのmin(ai,bi)の合計が最大になります.
例1:
入力:[1,4,3,2]
出力:4
nは2に等しく、最大総和は4=min(1,2)+min(3,4)である.
ヒント:
1.nは正の整数で、範囲は[1,10000].2.配列中の要素の範囲は[-1000,10000]である.
考え方:本題の構想は肝心で、まず問題の意味によって1からnまでのmin(ai,bi)の総和を最大にするには、2つの数の差が小さいほど、総和が大きくなる を導くことができる.ですので、昇順に並べ替えてから、項目ごとに を加算します.
長さ2 nの配列を指定すると、これらの数をn対に分けることができます.例えば、(a 1,b 1)、(a 2,b 2)、...,(an,bn)、1からnまでのmin(ai,bi)の合計が最大になります.
例1:
入力:[1,4,3,2]
出力:4
nは2に等しく、最大総和は4=min(1,2)+min(3,4)である.
ヒント:
1.nは正の整数で、範囲は[1,10000].2.配列中の要素の範囲は[-1000,10000]である.
class Solution {
public int arrayPairSum(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for(int i = 0; i < nums.length; i += 2)
sum += nums[i];
return sum;
}
}
考え方: