Python陣列區域性極值個數程式

在這篇文章中，我們將學習一個用於計算陣列中區域性極值個數的Python程式。

極值是指大於或小於其兩個相鄰元素的元素。

假設我們有一個包含n個元素的陣列。現在我們將找到指定輸入陣列中區域性極值個數。

注意

The first and last elements are not extrema.

使用For迴圈

注意

Both array[0] and array[n-1] have only one neighbor each, hence they are neither minima nor maxima.

len() − len() 方法返回物件中的專案數。當物件是字串時，len() 函式返回字串中字元的個數。

演算法（步驟）

以下是執行所需任務的演算法/步驟：−

  • 建立一個函式findExtrema()，該函式透過接受輸入陣列和陣列長度作為引數來返回陣列中的區域性極值。

  • 建立一個變數來儲存陣列中區域性極值的個數。

  • 使用for迴圈，使用len()函式遍歷從陣列的第一個元素到陣列長度。

  • 在任何給定時間，以下條件中只有一個為真：a[i]大於鄰居或小於鄰居。

  • 使用if條件語句檢查a[i]是否大於其兩個鄰居，並將結果新增到計數中。

  • 同樣，使用if條件語句檢查a[i]是否小於其兩個鄰居，並將結果新增到計數中。

  • 使用return語句返回計數。

  • 建立一個變數來儲存輸入陣列並列印給定的輸入陣列。

  • 使用len()函式（物件中的專案數）獲取輸入陣列的長度。

  • 透過將輸入陣列和陣列長度作為引數傳遞給它來呼叫findExtrema()函式，以列印陣列中區域性極值的個數。

示例

下面的程式使用for迴圈返回陣列中區域性極值的個數：−

# creating a function that returns the local extrema
# in an array by accepting input array,
# array length as arguments
def findExtrema(inputArray, arrayLength):
   # storing the count of no of local extrema in an array
   outputCount = 0
   # traversing from the first index to the length of the given array
   for k in range(1, arrayLength - 1):
      # At any given time, only one of the following conditions will be true:
      # either a[i] will be greater than neighbors or less than neighbors.
      # check if a[i] if greater than both its neighbours
      # Here it increments the output count by 1 if the condition is true
      # Else it increments output count by 0(same value) if condition is False
      outputCount += (inputArray[k] > inputArray[k - 1] and inputArray[k] > inputArray[k + 1])
      # check if a[i] if lesser than both its neighbours
      outputCount += (inputArray[k] < inputArray[k - 1] and inputArray[k] < inputArray[k + 1])
   # returning the number of local extrema of the given array
   return outputCount
# input array
inputArray = [5, 0, 1, 2, 1, 0, 3, 4, 1, 2]
# getting the length of an array
arrayLength = len(inputArray)
# Printing the given array
print("The Given Array is:", inputArray)
# calling the findExtrema() function by passing the
# input array and array length as arguments to it.
print("The Number of local extrema is:", findExtrema(inputArray, arrayLength))

輸出

執行上述程式將生成以下輸出：−

The Given Array is: [5, 0, 1, 2, 1, 0, 3, 4, 1, 2]
The number of local extrema is: 5

時間複雜度：O(n)

輔助空間：O(1)

因為沒有使用更多空間，所以空間複雜度為O(1)。

因為我們只使用for迴圈迭代列表，所以時間複雜度為O(N)，其中N是給定列表或陣列中元素的個數。

結論

在本文學習了局部極值之後，我們使用了Python的for迴圈來實現相同的問題。

更新於：2023年1月31日

瀏覽量：362

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告