leetcode
leetcode 1851 ~ 1900
分享 K 个糖果后独特口味的数量

分享 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)

代码细节讲解

🦆
为什么选择滑动窗口方法来解决这个问题,这种方法相比其他可能的方法有哪些优势?
滑动窗口方法在处理固定大小的连续子数组问题时非常有效,主要优势在于它的时间复杂度通常为O(n),可以通过一次遍历完成计算。同时,这种方法通过更新窗口边界来避免重复计算,使得算法更加高效。对于这类需要计算连续子数组特定属性(如独特元素数量)的问题,滑动窗口提供了一种直观且易于实现的解决方案。
🦆
在题解中的cnt数组大小为100001,这个大小是怎样确定的,与输入数据的范围有何关系?
cnt数组的大小设定为100001是基于假设糖果的口味种类可能很多,通常这个数组的大小设置应当覆盖所有可能的糖果口味的值。具体的大小取决于问题描述中糖果口味的可能最大值。如果题目没有明确指出糖果口味的最大值,通常需要根据题目的上下文或示例输入推断。在实际情况下,可根据具体的输入范围调整数组大小以提高空间效率。
🦆
题解中提到了`初始化窗口,移除前k个糖果`,是否有错误在操作顺序或者解释上?因为按照通常逻辑应该是先初始化窗口计数后再进行移动和调整。
确实,题解中的描述有误。按照常规的滑动窗口方法,应该首先通过遍历前k个糖果来初始化窗口内的计数,然后再根据窗口向右移动逐步更新计数和记录结果。题解中提前“移除前k个糖果”的表述可能是指在窗口首次滑动前,对于初始窗口内的糖果进行计数后再开始移动窗口。这应该是对过程描述的一个误导或者表达不清,正常操作应该是初始化后再滑动和调整。

相关问题