分享 K 个糖果后独特口味的数量
难度:
标签:
题目描述
代码结果
运行时间: 125 ms, 内存: 31.8 MB
// Problem: Leetcode 2107 - Number of Unique Flavors After Sharing K Candies
// Given a list of candies, where each candy has a unique flavor, the task is to find the number of unique flavors left after sharing exactly K candies.
// Approach:
// 1. Use Java Streams to filter and count unique flavors after sharing K candies.
// 2. Utilize the distinct() method to find unique elements and limit() to consider only the first K elements.
import java.util.Arrays;
import java.util.Set;
import java.util.stream.Collectors;
public class SolutionStream {
public int shareCandies(int[] candies, int k) {
Set<Integer> uniqueFlavors = Arrays.stream(candies)
.limit(k)
.boxed()
.collect(Collectors.toSet());
return uniqueFlavors.size();
}
}
解释
方法:
这个题解主要使用了滑动窗口的方法来解决问题。首先,通过一个固定大小为k的窗口来计算出窗口内独特口味的糖果数量。使用一个数组cnt来记录每种口味糖果的出现次数,同时使用一个变量p来记录当前窗口中独特口味的数量。遍历所有糖果,首先更新cnt数组,当某种口味糖果第一次出现时,p增加1。接着,从第k个糖果开始,每次窗口向右移动一位,移除窗口最左侧的糖果,并添加新的糖果到窗口,同时更新cnt数组和p的值。最后,使用一个变量ans来记录窗口移动过程中p的最大值,即为答案。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择滑动窗口方法来解决这个问题,这种方法相比其他可能的方法有哪些优势?
▷🦆
在题解中的cnt数组大小为100001,这个大小是怎样确定的,与输入数据的范围有何关系?
▷🦆
题解中提到了`初始化窗口,移除前k个糖果`,是否有错误在操作顺序或者解释上?因为按照通常逻辑应该是先初始化窗口计数后再进行移动和调整。
▷