Python - 最小相同连续子数组

我们的问题是在给定数组中找到最小相同连续子数组，并使用 Python 实现该算法。因此，我们将使用 Python 的基本功能来获得所需的结果。

理解问题

在给定的问题陈述中，我们需要找到给定输入数组中存在的最小相同连续子数组。因此，我们将拥有一个包含一些重复项的数组，并且我们必须显示具有最小重复项计数的子数组。例如：假设我们有一个数组 [0, 0, 2, 2, 2, 3, 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 永远不会引发 KeyError。它为不存在的键提供默认值。例如 -

示例

from collections import defaultdict

def default_value():
   return "Not available"
   
# Define the dict
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

# initializing the array list
array_items =  [0, 0, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5]

# printing original list
print("The original list is : " + str(array_items))

# create a dictionary for keep tracking of frequency
frequency = defaultdict(int)
for item in array_items:
   frequency[item] += 1

# Get the minimum value in the above dictionary
min_value = min(frequency.values())

# Now find the item with minimum frequency
for item, count in frequency.items():
   if count == min_value:
      min_item = item
      break

# print the result
print("Minimum identical consecutive Subarray number is : " + str(min_item))

输出

The original list is : [0, 0, 2, 2, 2, 3, 3, 3, 3, 5, 5, 5]
Minimum identical consecutive Subarray number is : 0

复杂度

因此，找到最小相同连续子数组的时间复杂度为 O(n)，其中 n 是给定输入数组中存在的项目数。这样做的原因是代码迭代数组的项目 n 次，并且我们还创建了一个大小为 n 的字典。

结论

结论是，我们创建了一个代码，使用 Python 中提供的 collections 模块来获取最小相同连续子数组。这是使用 O(n) 的时间复杂度来获得所需结果的直接方法。

更新于: 2023年10月16日

53 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告