前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2022-05-02:给定一个数组arr,一个正数num,一个正数k,可以把arr中的某些数字拿出来组成一组,要求该组中的最大值

2022-05-02:给定一个数组arr,一个正数num,一个正数k,可以把arr中的某些数字拿出来组成一组,要求该组中的最大值

作者头像
福大大架构师每日一题
发布2022-06-04 10:44:11
6790
发布2022-06-04 10:44:11
举报

2022-05-02:给定一个数组arr,一个正数num,一个正数k,

可以把arr中的某些数字拿出来组成一组,要求该组中的最大值减去最小值<=num,

且该组数字的个数一定要正好等于k,

每个数字只能选择进某一组,不能进多个组。

返回arr中最多有多少组。

来自微软。

答案2022-05-02:

排序+动态规划。滑动窗口有陷阱,不一定行,可能可以。

第一种情况,包含i,dp[i]跟dp[i-k]相关。

第二种情况,不包含i,dp[i]=dp[i-1]。

时间复杂度O(N * logN)。

代码用rust编写。代码如下:

代码语言:javascript
复制
fn main() {
    let mut arr: Vec<isize> = vec![1, 2, 3, 3, 3, 10, 10, 10, 100, 100, 100];
    let ans = max_teams2(&mut arr, 3, 3);
    println!("ans = {}", ans);
}

// 时间复杂度O(N * logN)
fn max_teams2(arr: &mut Vec<isize>, num: isize, k: isize) -> isize {
    let n: isize = arr.len() as isize;
    if k > n {
        return 0;
    }
    arr.sort_unstable();
    let mut dp: Vec<isize> = vec![];
    for _ in 0..n {
        dp.push(0);
    }
    dp[(k - 1) as usize] = if arr[(k - 1) as usize] - arr[0] <= num {
        1
    } else {
        0
    };
    for i in k..n {
        let p1 = dp[(i - 1) as usize];
        let p2 = if arr[i as usize] - arr[(i - k + 1) as usize] <= num {
            1
        } else {
            0
        } + dp[(i - k) as usize];
        dp[i as usize] = get_max(p1, p2);
    }
    return dp[(n - 1) as usize];
}

fn get_max(a: isize, b: isize) -> isize {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下:

***

[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_02_3_week/Code04_MaxTeamNumber.java)

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

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

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

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

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