2021-08-10：给定一个正数数组arr，返回arr的子集不能累加出的最小正数。1）正常怎么做？ 2）如果arr中肯定有1这个值，怎么做？
福大大 答案2021-08-10：
先排序，然后扩充range范围。
1.b<=range 1,扩充到range b。
2.b>range 1,直接返回range 1。
时间复杂度：排序的。
空间复杂度：排序的。
代码用golang编写。代码如下：
代码语言：txt复制package main
import (
"fmt"
"math"
"sort"
)
func main() {
arr := []int{1, 2, 5}
if true {
ret := unformedSum1(arr)
fmt.Println(ret)
}
if true {
ret := unformedSum2(arr)
fmt.Println(ret)
}
if true {
ret := unformedSum3(arr)
fmt.Println(ret)
}
}
func unformedSum1(arr []int) int {
if len(arr) == 0 {
return 1
}
set := make(map[int]struct{})
process(arr, 0, 0, set)
min := math.MaxInt64
for i := 0; i != len(arr); i {
min = getMin(min, arr[i])
}
for i := min 1; i != math.MinInt64; i {
if _, ok := set[i]; !ok {
return i
}
}
return 0
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func process(arr []int, i int, sum int, set map[int]struct{}) {
if i == len(arr) {
set[sum] = struct{}{}
return
}
process(arr, i 1, sum, set)
process(arr, i 1, sum arr[i], set)
}
func unformedSum2(arr []int) int {
if len(arr) == 0 {
return 1
}
sum := 0
min := math.MaxInt64
for i := 0; i != len(arr); i {
sum = arr[i]
min = getMin(min, arr[i])
}
// boolean[][] dp ...
N := len(arr)
dp := make([][]bool, N)
for i := 0; i < N; i {
dp[i] = make([]bool, sum 1)
}
for i := 0; i < N; i { // arr[0..i] 0
dp[i][0] = true
}
dp[0][arr[0]] = true
for i := 1; i < N; i {
for j := 1; j <= sum; j {
if j-arr[i] >= 0 {
dp[i][j] = dp[i-1][j] || (dp[i-1][j-arr[i]])
} else {
dp[i][j] = dp[i-1][j] || (false)
}
}
}
for j := min; j <= sum; j {
if !dp[N-1][j] {
return j
}
}
return sum 1
}
// 已知arr中肯定有1这个数
func unformedSum3(arr []int) int {
if len(arr) == 0 {
return 0
}
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j] // O (N * logN)
})
range2 := 1
// arr[0] == 1
for i := 1; i != len(arr); i {
if arr[i] > range2 1 {
return range2 1
} else {
range2 = arr[i]
}
}
return range2 1
}执行结果如下：
图片左神java代码
