資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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) 的時間複雜度來獲得所需結果的直接方法。
53 次檢視
