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循环来实现相同的问题。