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

福大大架构师每日一题

发布于 2023-07-25 09:04:02

23400

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 为之前的计数 cnt 和 maxCnt 中的较大值，并将 cnt 重置为 1。
• 否则，递增序列继续，将 cnt 自增 1。

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

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;
}