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

开启你的职业生涯

完成课程获得认证

开始学习
广告