难度: Medium
Submission
运行时间: 159 ms
内存: 34.2 MB
from typing import List
class Solution:
def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
ans = []
window = {} # 哈希表，用于记录当前窗口中的数字及其出现次数
# 初始化第一个窗口
for i in range(k):
if nums[i] in window:
window[nums[i]] += 1
else:
window[nums[i]] = 1
ans.append(len(window))
# 滑动窗口
for i in range(k, n):
window[nums[i-k]] -= 1 # 移除窗口最左侧的数字的出现次数
if window[nums[i-k]] == 0:
del window[nums[i-k]] # 如果数字的出现次数为0，则从哈希表中删除该数字
if nums[i] in window:
window[nums[i]] += 1
else:
window[nums[i]] = 1 # 添加窗口最右侧的数字及其出现次数
ans.append(len(window)) # 记录当前窗口的数字种类数
return ans
Explain
该题解采用了滑动窗口的方法来解决问题。首先，利用一个字典来记录每个窗口中的元素及其对应的出现次数。初始化时，填充第一个窗口，并计算其中不同数字的数量，即字典的键的数量。随后，窗口开始向右滑动，每次移动时，从字典中减去左边界的元素计数，并可能将其删除（如果计数为0）。同时，添加新的右边界元素到字典中。每次滑动后，字典的大小（即不同数字的数量）被记录到结果列表中。
时间复杂度: O(n)
空间复杂度: O(n)
from typing import List
class Solution:
def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
n = len(nums) # 数组的总长度
ans = [] # 用于存储每个窗口的不同数字数量
window = {} # 哈希表，用于记录当前窗口中的数字及其出现次数
# 初始化第一个窗口
for i in range(k):
if nums[i] in window:
window[nums[i]] += 1 # 如果数字已存在，增加其计数
else:
window[nums[i]] = 1 # 如果数字不存在，添加到字典并计数为1
ans.append(len(window)) # 记录当前窗口的数字种类数
# 滑动窗口
for i in range(k, n):
window[nums[i-k]] -= 1 # 移除窗口最左侧的数字的出现次数
if window[nums[i-k]] == 0:
del window[nums[i-k]] # 如果数字的出现次数为0，则从哈希表中删除该数字
if nums[i] in window:
window[nums[i]] += 1 # 如果数字已存在，增加其计数
else:
window[nums[i]] = 1 # 添加窗口最右侧的新数字及其出现次数
ans.append(len(window)) # 记录当前窗口的数字种类数
return ans
Explore
从字典中删除出现次数为0的数字可以减少字典的大小，这样可以节省空间并提高查询和更新操作的效率。此外，这种做法可以直接使用字典的键的数量来确定窗口中不同数字的种类数，从而简化了求解过程。
在提供的解法中，并没有明确处理数组长度小于窗口长度k的情况。如果数组长度小于k，初始化窗口的循环将会导致索引越界错误。因此，解法应该在开始时添加一个检查，确保k不大于数组长度，以处理这种边界情况。
在滑动窗口算法中，字典用于记录每个数字的出现次数。即使数组中有重复元素，也不会影响窗口中元素种类数量的计算，因为字典的键是唯一的。重复元素只会增加特定键的计数，但不会增加字典的键的总数，因此种类数仍然准确。