Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit668447c

Browse files
committed
add 561 solution
1 parentd1eef90 commit668447c

File tree

3 files changed

+127
-0
lines changed

3 files changed

+127
-0
lines changed

‎src/0561.Array-Partition-I/README.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
#[561. Array Partition I][title]
2+
3+
##Description
4+
5+
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
6+
**Example 1:**
7+
8+
```
9+
Input: [1,4,3,2]
10+
11+
Output: 4
12+
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
13+
14+
Note:
15+
n is a positive integer, which is in the range of [1, 10000].
16+
All the integers in the array will be in the range of [-10000, 10000].
17+
```
18+
**Tags:** Math, String
19+
20+
##题意
21+
>给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1,b1),(a2,b2),…,(an,bn)(a1,b1),(a2,b2),…,(an,bn) ，
22+
>使得从 1 到 n 的 min(ai,bi)min(ai,bi) 总和最大
23+
24+
##题解
25+
26+
###思路1
27+
>很容易想到，让两个比较小的数在一起比一个小的一个大的数放在一起产生的结果要大。
28+
故可以先将数组排序，然后从头开始相邻两个整数放在一起，这样子可以产生最大的结果。
29+
30+
- 时间复杂度
31+
对数组进行排序，故时间复杂度为 O(nlogn)。
32+
33+
```go
34+
funcarrayPairSum(nums []int)int {
35+
sort.Ints(nums)
36+
ans:=0
37+
fori:=0; i <len(nums); i +=2 {
38+
ans += nums[i]
39+
}
40+
return ans
41+
}
42+
```
43+
44+
###思路2
45+
>思路2
46+
```go
47+
48+
```
49+
50+
##结语
51+
52+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
53+
54+
[title]:https://leetcode.com/problems/array-partition-i/
55+
[me]:https://github.com/kylesliu/awesome-golang-leetcode
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package Solution
2+
3+
import"sort"
4+
5+
funcarrayPairSum(nums []int)int {
6+
sort.Ints(nums)
7+
ans:=0
8+
fori:=0;i<len(nums);i+=2 {
9+
ans+=nums[i]
10+
}
11+
returnans
12+
}
13+
14+
funcSort(nums []int) []int {
15+
iflen(nums)==0 {
16+
return []int{}
17+
}
18+
max:=nums[0]
19+
varleft_res,right_res,res []int
20+
fori:=1;i<len(nums);i++ {
21+
ifnums[i]<max {
22+
left_res=append(left_res,nums[i])
23+
}else {
24+
right_res=append(right_res,nums[i])
25+
}
26+
}
27+
left_res=Sort(left_res)
28+
right_res=Sort(right_res)
29+
res=append(res,left_res...)
30+
res=append(res,max)
31+
res=append(res,right_res...)
32+
returnres
33+
}
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
expectint
15+
}{
16+
{"TestCase", []int{1,4,3,2},4},
17+
}
18+
19+
//开始测试
20+
fori,c:=rangecases {
21+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
22+
got:=arrayPairSum(c.inputs)
23+
if!reflect.DeepEqual(got,c.expect) {
24+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
25+
c.expect,got,c.inputs)
26+
}
27+
})
28+
}
29+
}
30+
31+
//压力测试
32+
funcBenchmarkSolution(b*testing.B) {
33+
34+
}
35+
36+
//使用案列
37+
funcExampleSolution() {
38+
39+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp