Python - 最小相同连续子数组
我们的问题是找到给定数组中的最小相同连续子数组，并使用 Python 实现此算法。因此，我们将使用 Python 的基本功能来获得所需的结果。
理解问题
在给定的问题陈述中，我们需要找到给定输入数组中存在的最短相同连续子数组。因此，我们将有一个包含一些重复项的数组，并且我们必须显示具有最少重复项计数的子数组。例如:假设我们有一个数组 [0, 0, 2, 2, 2, 3, 3, 3, 5, 5, 5]，因此在这个数组中，0 是在给定数组中出现两次的数字，而其他数字出现三次和四次。因此结果将为 0。
上述问题的逻辑
为了解决这个问题，我们将使用 Python 中的 collections 模块。借助此模块，我们将使用 defaultdict 类并创建给定数组的字典。因此，通过使用此字典，我们将能够找到数组的最小值和最大值。之后，我们将找到数组中频率最小的项并返回频率最小的项。
Python 中的 collections 模块是什么?
在 Python 中，有一个 collections 模块用于实现专门的容器数据类型，以提供内置容器(如 dict、list、set 和 tuple)的替代方案。此模块中存在的一些有用的数据结构是 namedtuple、counter、defaultdict 和 ordereddict。因此，我们将在此程序中使用 defaultdict。
defaultdict 将简单地创建我们尝试访问的任何项目。 defaultdict 也是一个类似字典的对象，也提供字典提供的方法。但两者的区别在于，defaultdict 将第一个参数作为字典的默认数据类型。defaultdict 永远不会引发 KeyError。它会为不存在的键提供默认值。例如 −
示例
from collections import defaultdict
def default_value():
return "Not available"
# 定义字典
dictry = defaultdict(default_value)
dictry["x"] = 10
dictry["y"] = 20
print(dictry["x"])
print(dictry["y"])
print(dictry["z"])
输出
10 20 Not available
算法
步骤 1 − 因为我们必须找出最小的相同连续子数组数。因此，正如我们上面所讨论的，首先我们将从 python 中的 collections 模块导入 defaultdict 类。
步骤 2 - 导入必要的模块后，我们将初始化数组项并将数组命名为 array_items。此数组将包含一些重复项，以查找最小相同子数组。
步骤 3 - 然后我们将创建一个字典来跟踪重复项的频率。我们必须得到最小频繁项。
步骤 4 - 现在我们有了数组中每个项的频率，因此在此步骤中，我们需要在上述字典中找到最小值。
步骤 5 - 结果，我们将在频率字典中找到具有最小频率的最小项。
示例
from collections import defaultdict
# 初始化数组列表
array_items = [0, 0, 2, 2, 2, 3, 3, 3, 5, 5, 5]
# 打印原始列表
print("原始列表是:" + str(array_items))
# 创建一个字典以跟踪频率
frequency = defaultdict(int)
for item in array_items:
frequency[item] += 1
# 获取上述字典中的最小值
min_value = min(frequency.values())
# 现在找到频率最小的项目
for item, count in frequency.items():
if count == min_value:
min_item = item
break
# 打印结果
print("最小相同连续子数组数为 : " + str(min_item))
输出
原始列表为:[0, 0, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5] 最小相同连续子数组数为 : 0
复杂度
因此，查找最小相同连续子数组的时间复杂度为 O(n)，其中 n 是给定输入数组中存在的项目数。原因是代码迭代数组的项目 n 次，并且我们创建了一个大小为 n 的字典。
结论
结论是，我们已经创建了一个代码，使用 Python 中的 collections 模块来获取最小相同连续子数组。这是获得所需结果的直接方法，时间复杂度为 O(n)。
