Java Program to Print All the Leaders in an Array

在编程领域，识别数据集中的特定元素对于各种分析任务至关重要。其中一个问题是确定数组中的领导者元素。

数组中的领导者

序列中的领导者被描述为大于其右侧所有其他元素的元素。让我们看一些例子。

数组中领导者的示例

示例-1

输入数组 [16, 17, 4, 3, 5, 2]

输出 17, 5

解释：在给定的数组中，17 大于其后的每个元素，而 5 大于后续元素 2。因此，它们是领导者。

示例-2

输入数组 [1, 2, 3, 4, 5]

输出 5

解释：在这个严格递增的数组中，唯一的领导者是 5，它是最后一个元素，并且大于其右侧的所有元素（无）。

暴力破解法

代码中使用的方法通过外部循环遍历每个元素来识别数组中的领导者。对于每个元素，它使用内部循环将其与所有后续元素进行比较。

如果当前元素大于其右侧的所有元素，则它被视为领导者并被打印。这种方法简单直观，可以清晰地识别数组中的领导者。

步骤 1：初始化一个大小为 n 的整数数组 arr。

步骤 2：获取数组的长度并将其存储在 n 中。如果 n 为 0，则打印“数组为空”并退出方法。

步骤 3：遍历从索引 0 到 n-1 的每个元素

步骤 4：初始化一个布尔标志 isLeader 为 true。

步骤 5：与右侧元素进行比较

• 对于从 i+1 到 n-1 的索引 j 处的每个元素，将其与 arr[i] 进行比较。
• 如果任何元素 arr[j] 大于或等于 arr[i]，则将 isLeader 设置为 false 并跳出内循环。

步骤 6：如果在内循环后 isLeader 仍然为 true，则打印 arr[i]，因为它是一个领导者。

让我们在 Java 程序中实现上述方法。

输出

 
42 14   

时间复杂度： O(n^2) 嵌套循环导致二次时间复杂度。

辅助空间： O(1) 仅使用了几个额外的变量。

从右到左遍历方法

该方法从右到左扫描数组，将最后一个元素作为初始领导者。当某个元素大于当前最大值时，它会更新并打印领导者。这种方法通过将每个元素与从右边看到的迄今为止的最大值进行比较来有效地识别领导者。

算法

步骤 1：初始化一个大小为 n 的整数数组 arr。

步骤 2：将 n 设置为 arr 的长度。

步骤 3：如果 n 为 0，则打印“数组为空”并退出方法。

步骤 4：初始化最大值

• 将 maxFromRight 设置为数组的最后一个元素 (arr[n - 1])。
• 打印 maxFromRight，因为最后一个元素始终是领导者。

步骤 5：对于从 n - 2 向下到 0 的每个索引 i

• 将当前元素 arr[i] 与 maxFromRight 进行比较。

步骤 6：如果 arr[i] 大于 maxFromRight

• 将 maxFromRight 更新为 arr[i]。
• 打印 arr[i]，因为它是一个新的领导者。

让我们在 Java 程序中实现上述方法。

输出

 
14 2   

复杂度

时间复杂度：该算法只遍历一次数组。由于它恰好处理每个元素一次，因此时间复杂度为 O(n)。

辅助空间：该方法使用恒定的额外空间。变量如 maxFromRight、n 和循环索引 i 被使用，它们的空间需求不取决于输入数组的大小。因此，空间复杂度为 O(1)。