Python中查找给定数组中领导者的三种方法

在本教程中，我们将编写 Python 代码来查找给定数组中的领导元素。前导元素是指数组中大于或等于其右侧所有元素的元素。换句话说，如果一个元素大于或等于数组中紧随其后的每个元素，则该元素被视为领导者。

让我们理解下面的例子 

n =  6  
A[] = [ 16 , 17 , 4 , 3 , 5 , 2 ]  
输出：  17 5 2    

解释 ：

  • 17 大于其右侧的所有元素（4、3、5、2）。
  • 5 大于其右侧的所有元素 (2)。
  • 2 是最右边的元素，因此它始终被视为领导者。

所以，这个数组中的领导者是 [17, 5, 2]

例子 -

  1. n =  5  
  2. A = [ 1 , 2 , 3 , 4 , 0 ]  
  3. 输出：  4 0   

解释 -
4 和 0，因为它们大于或等于其右侧的所有元素。

解决方案
我们将使用各种方法来解决这个问题。
幼稚的方法

  1. 初始化一个空列表来存储领导者。
  2. 开始从最左边的元素到倒数第二个元素（不包括最后一个元素，因为它始终是前导元素）迭代数组。
  3. 对于索引 i 处的每个元素 A：
    2. 将标志变量 is_leader 初始化为 True，假设 A 最初被视为领导者。
    3. 开始迭代 A 右侧的元素，从 A[i+1] 到最后一个元素。
    4. 对于 A 右侧的每个元素 A[j]：如果 A[j] 大于或等于 A，则继续检查下一个元素。如果 A[j] 小于 A，则将 is_leader 设置为 False 并跳出循环，因为 A 不能成为领导者。
    5. 检查完 A 右边的所有元素后，如果 is_leader 仍然为 True，则说明 A 是领导者。将 A 添加到领导者列表中。
  4. 循环结束后，领导者列表将包含数组中找到的所有领导者。

def find_leaders(arr):  
    n = len(arr)  
    leaders = []  
  
    # 从左到右遍历数组  ；
    for i in range(n - 1):  
        is_leader = True  # Assume arr[i] is a leader initially  
  
        # 将 arr[i] 与其右侧的元素进行比较  ；
        for j in range(i + 1, n):  
            if arr[i] < arr[j]:  
                is_leader = False  # arr[i] is not a leader  
                break  # No need to check further  
  
        如果 is_leader 仍然为 True，则 arr[i] 是领导者  ；
        if is_leader:  
            leaders.append(arr[i])  
  
    # The rightmost element is always a leader  
    leaders.append(arr[n - 1])  
  
    return leaders  
  
# Example usage:  
arr = [1, 2, 3, 4, 0]  
result = find_leaders(arr)  
print("Leaders in the array:", result)  

  • 我们定义一个函数 find_leaders() ，它接受数组 arr 作为输入。
  • 我们初始化空列表领导者来存储在数组中找到的领导者。
  • 我们使用两个嵌套循环从左到右遍历数组。外部循环从第一个元素到倒数第二个元素迭代元素，内部循环将每个元素与其右侧的元素进行比较。
  • 我们使用布尔变量 is_leader 来假设当前元素最初是领导者。
  • 在内部循环中，如果我们发现任何大于当前元素的元素，我们将 is_leader 设置为 False 并退出循环，因为当前元素不能是领导者。
  • 如果检查右侧所有元素后 is_leader 仍然为 true，则意味着当前元素是领导者，因此我们将其追加到领导者列表中。
  • 最后，我们将最右边的元素（最后一个元素）附加到领导者列表中，因为它始终是领导者。

在数组中查找领导者的简单方法的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

方法 - 2：通过查找后缀最大值来查找领导者
查找数组中的后缀最大值意味着找出数组中特定元素右侧的元素（包括该元素本身）中的最大值。

下面是后缀最大值的实现方法。

  • 首先初始化一个变量来跟踪从右到左遍历数组时遇到的最大值。
  • 开始从右到左迭代数组。
  • 在每一步中，将当前元素与迄今为止遇到的最大值（在步骤 1 中初始化）进行比较。
  • 如果当前元素大于最大值，则将最大值更新为当前元素，因为它代表当前元素右侧的最大值。
  • 对数组中的所有元素继续此过程，有效地找到每个元素后缀（右侧元素）中的最大值。
  • 当您遍历数组时，记录或打印每个元素遇到的最大值。这些记录的值表示原始数组中相应元素的后缀最大值。

让我们理解下面的例子 -

def find_leaders(arr):  
    n = len(arr)  
    leaders = []  # To store the leader elements  
  
    # 将右边最大的元素初始化为最右边的元素  ；
    max_right = arr[n - 1]  
  
    # 最右边的元素总是领导者  ；
    leaders.append(max_right)  
  
    # 从右向左遍历数组  ；
    for i in range(n - 2, -1, -1):  
        # 如果当前元素大于或等于右侧元素的最大值 ；
        if arr[i] >= max_right:  
            从右侧更新最大值；
            max_right = arr[i]  
            # 将领导者元素添加到领导者列表  ；
            leaders.append(max_right)  
  
    # 反转领导列表，按原始顺序获取元素  ；
    leaders.reverse()  
  
    return leaders  
  
# Example usage:  
arr = [16, 17, 4, 3, 5, 2]  
result = find_leaders(arr)  
print("Leaders in the array:", result)  

  • 我们定义一个函数 find_leaders ，它接受数组 arr 作为输入。
  • 我们找到数组 n 的长度并初始化空列表领导者来存储领导者元素。
  • 我们首先使用数组最右边的元素（即 arr[n - 1]）初始化 max_right 变量。最右边的元素始终是领导者，因此我们将其添加到领导者列表中。
  • 然后，我们以相反的顺序（从右到左）从倒数第二个元素（索引 n - 2）到第一个元素（索引 0）迭代数组。
  • 在循环内，我们将每个元素与当前的 max_right 进行比较。如果当前元素大于或等于 max_right，则它成为新的领导者，我们相应地更新 max_right。
  • 当遇到每个领导者元素时，我们将其添加到领导者列表中。
  • 循环结束后，我们反转领导列表以按原始顺序获取元素。
  • 最后，我们返回包含数组中所有领导者元素的领导者列表。

在示例用法中，我们使用示例数组调用 find_leaders 函数并打印在数组中找到的领导者。

方法 - 3：基于堆栈的方法
以前的方法提供了线性时间复杂度，但它没有保持元素在输入数组中出现的顺序。为了在寻找领导者的同时保留元素的原始顺序，我们可以使用堆栈数据结构。

以下是使用基于堆栈的方法识别阵列中的领导者的修订步骤：
[list=1]

  • 从数组的最后一个索引开始该过程。最右边的元素始终是领导者，因为其右侧没有元素。
  • 继续以相反的顺序迭代数组，向索引位置 0 移动。
  • 维护遍历数组时遇到的最大值的记录。
  • 每当遇到大于之前记录的最大值的元素时，就将其视为领导者并将其压入堆栈。
  • 完成迭代后，遍历堆栈并打印其内容，因为这些元素代表原始数组中的前导元素。
    让我们理解下面的例子。

    def find_leaders(arr):  
        n = len(arr)  
        stack = []  
        max_element = arr[n - 1]  # Initialize the maximum element as the last element  
      
        # The rightmost element is always a leader  
        stack.append(max_element)  
      
        # 从倒数第二个元素迭代到第一个元素  ；
        for i in range(n - 2, -1, -1):  
            if arr[i] >= max_element:  
                # 如果当前元素大于或等于迄今为止的最大元素， 
                  # 它就是领导者  ；
                stack.append(arr[i])  
                max_element = arr[i]  # Update the maximum element  
      
        # 按照输入数组中出现的顺序打印领导人  ；
        while stack:  
            print(stack.pop(), end=" ")  
    # Example usage:  
    arr = [1, 2, 3, 4, 0]  
    find_leaders(arr)  

    • 我们定义一个函数 find_leaders ，它接受数组 arr 作为输入。
    • 我们计算输入数组 n 的长度并初始化一个空堆栈来存储前导。
    • 我们将 max_element 初始化为输入数组的最后一个元素，因为最右边的元素始终是前导元素。我们将这个最大元素压入堆栈以开始。
    • 然后，我们使用 for 循环以相反的顺序从倒数第二个元素（索引 n-2）到第一个元素（索引 0）迭代数组。
    • 在循环内部，我们将当前元素 arr 与 max_element 进行比较。如果当前元素大于或等于 max_element，则将其视为领导者，因此我们将其压入堆栈。如果 max_element 更大，我们还会将其更新为当前元素。
    • 遍历数组后，我们已经识别出领先者并将其存储在堆栈中。
    • 最后，我们通过从堆栈中弹出元素并打印它们，以与输入数组中出现的顺序相同的顺序打印前导。

    结论
    在本教程中，我们学习了如何在数组中查找领导元素，这些元素大于或等于其右侧的所有元素。我们探索了三种不同的方法，例如简单的方法，它涉及迭代数组并将每个元素与其右侧的元素进行比较。它的时间复杂度为O(n 2 )。通过查找后缀最大值来查找领导者，我们通过查找每个元素右侧的最大元素来优化流程。它实现了 O(n) 的线性时间复杂度并保留了元素的顺序。而基于堆栈的方法用于维护元素的原始顺序，我们使用了堆栈。从最右边的元素开始，我们反向迭代数组，将前导元素推入堆栈。该方法的时间复杂度也为 O(n)