2023-07-15:给你一个 非递减 的正整数数组 nums 和整数 K, 判断该数组是否可以被分成一个或几个 长度至少 为

举报
福大大架构师每日一题 发表于 2023/07/15 21:55:08 2023/07/15
【摘要】 2023-07-15:给你一个 非递减 的正整数数组 nums 和整数 K,判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。输入:nums = [1,2,2,3,3,4,4], K = 3。输出:true。答案2023-07-15: 大体步骤如下:1.初始化计数变量 cnt 和最大计数变量 maxCnt,初始值都为 1。2.从索引 1 开始遍历数组 nums:如...

2023-07-15:给你一个 非递减 的正整数数组 nums 和整数 K,

判断该数组是否可以被分成一个或几个 长度至少 为 K 的 不相交的递增子序列。

输入:nums = [1,2,2,3,3,4,4], K = 3。

输出:true。

答案2023-07-15:

大体步骤如下:

1.初始化计数变量 cnt 和最大计数变量 maxCnt,初始值都为 1。

2.从索引 1 开始遍历数组 nums

  • 如果 nums[i-1] 不等于 nums[i],说明遇到了一个新的递增序列,更新 maxCnt 为之前的计数 cntmaxCnt 中的较大值,并将 cnt 重置为 1。

  • 否则,递增序列继续,将 cnt 自增 1。

3.遍历结束后,再次更新 maxCnt 为最后一个递增序列的计数 cntmaxCnt 中的较大值。

4.判断长度为 len(nums) 除以 maxCnt 后是否大于等于 k,如果是,返回 true;否则,返回 false

5.在 main 函数中,定义数组 nums 和整数 k

6.调用函数 canDivideIntoSubsequences(nums, k) 并将结果赋给变量 result

7.输出结果 Result: true

时间复杂度:
遍历数组 nums 的时间复杂度为 O(n),其中 n 是数组 nums 的长度。
因此,整个算法的时间复杂度为 O(n)。

空间复杂度:
算法使用了常数级别的额外空间,不随输入规模变化,所以空间复杂度为 O(1)。

go完整代码如下:

package main

import (
    "fmt"
)

func canDivideIntoSubsequences(nums []int, k int) bool {
    cnt := 1
    maxCnt := 1

    for i := 1; i < len(nums); i++ {
        if nums[i-1] != nums[i] {
            maxCnt = max(maxCnt, cnt)
            cnt = 1
        } else {
            cnt++
        }
    }

    maxCnt = max(maxCnt, cnt)
    return len(nums)/maxCnt >= k
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    nums := []int{1, 2, 2, 3, 3, 4, 4}
    k := 3

    result := canDivideIntoSubsequences(nums, k)
    fmt.Println("Result:", result)
}

在这里插入图片描述

rust完整代码如下:

fn can_divide_into_subsequences(nums: &[i32], k: i32) -> bool {
    let mut cnt = 1;
    let mut max_cnt = 1;

    for i in 1..nums.len() {
        if nums[i - 1] != nums[i] {
            max_cnt = max_cnt.max(cnt);
            cnt = 1;
        } else {
            cnt += 1;
        }
    }

    max_cnt = max_cnt.max(cnt);
    nums.len() as i32 / max_cnt >= k
}

fn main() {
    let nums = vec![1, 2, 2, 3, 3, 4, 4];
    let k = 3;

    let result = can_divide_into_subsequences(&nums, k);
    println!("Result: {}", result);
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool canDivideIntoSubsequences(vector<int>& nums, int k) {
    int cnt = 1;
    int maxCnt = 1;

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i - 1] != nums[i]) {
            maxCnt = max(maxCnt, cnt);
            cnt = 1;
        }
        else {
            cnt++;
        }
    }

    maxCnt = max(maxCnt, cnt);
    return nums.size() / maxCnt >= k;
}

int main() {
    vector<int> nums = { 1, 2, 2, 3, 3, 4, 4 };
    int k = 3;

    bool result = canDivideIntoSubsequences(nums, k);
    cout << "Result: " << boolalpha << result << endl;

    return 0;
}

在这里插入图片描述

c完整代码如下:

#include <stdio.h>

int canDivideIntoSubsequences(int nums[], int length, int k) {
    int cnt = 1;
    int maxCnt = 1;

    for (int i = 1; i < length; i++) {
        if (nums[i - 1] != nums[i]) {
            if (maxCnt < cnt) {
                maxCnt = cnt;
            }
            cnt = 1;
        }
        else {
            cnt++;
        }
    }

    if (maxCnt < cnt) {
        maxCnt = cnt;
    }

    return (length / maxCnt) >= k;
}

int main() {
    int nums[] = { 1, 2, 2, 3, 3, 4, 4 };
    int length = sizeof(nums) / sizeof(nums[0]);
    int k = 3;

    int result = canDivideIntoSubsequences(nums, length, k);
    printf("Result: %s\n", result ? "true" : "false");

    return 0;
}

在这里插入图片描述

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。