前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-10:给定一个正数数组arr,返回arr的子集不能累加出的最小正数。1)正常怎么做? 2)如果arr中肯定有1这

2021-08-10:给定一个正数数组arr,返回arr的子集不能累加出的最小正数。1)正常怎么做? 2)如果arr中肯定有1这

作者头像
福大大架构师每日一题
发布2021-09-03 15:22:03
3190
发布2021-09-03 15:22:03
举报

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编写。代码如下:

代码语言:javascript
复制
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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class16/Code02_SmallestUnFormedSum.java)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档