2023-07-15:给你一个 非递减 的正整数数组 nums 和整数 K, 判断该数组是否可以被分成一个或几个 长度至少 为
【摘要】 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
为之前的计数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;
}
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)