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]是否小于它的两个邻居，并将结果加到计数中。

• 使用返回语句返回计数。

• 创建一个变量来存储一个输入数组并打印给定的输入数组。

• 使用 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 循环来实现同样的问题。