在数组中查找引线leaders

Question

我们需要打印数组中存在的所有leaders。如果元素大于元素的右侧，则元素是领导者。
例如：

arr[]={14, 12, 70, 15, 99, 65, 21, 90}
Here 99 and 90 are leader elements

Answer 1

使用两个循环。外循环迭代数组元素，内循环检查数组的正确元素。如果当前元素大于右侧元素，则它是leaders。
java代码：

public static void findLeadersInAnArrayBruteForce(int arr[])
 {
 System.out.println("Finding leaders in an array using brute force : ");
 for (int i = 0; i < arr.length; i++) {
 boolean isLeader=true;
 for (int j = i+1; j < arr.length; j++) {
 if(arr[i] <= arr[j])
 { 
 isLeader=false;
 break;
 } 
 }
 if(isLeader)
 System.out.print(arr[i]+" ");
 }
 }

时间复杂度：o(N^2)

解决方案2：
让我们找到更优化的解决方案
我们将使用最右边的元素始终是leaders的属性。

我们将从最右边的元素开始并跟踪最大值。
每当我们获得新的最大值时，该元素就是leaders。
java代码：

public static void findLeadersInAnArray(int arr[])
 {
  System.out.println("Finding leaders in an array : ");
  int rightMax=arr[arr.length-1];
  // Rightmost will always be a leader
  System.out.print(rightMax+" ");
  for (int i = arr.length-2; i>=0; i--) {
   if(arr[i] > rightMax)
   {
    rightMax=arr[i];
    System.out.print(" "+rightMax);
   }
  }
 }

时间复杂度：o(N)

在数组中查找leaders的 Java 程序：

package org.arpit.java2blog;

public class FindLeadersInArrayMain {

 public static void main(String[] args) {
  int arr[]={14, 12, 70, 15, 99, 65, 21, 90};
  findLeadersInAnArrayBruteForce(arr);
  System.out.println("n==================");
  findLeadersInAnArray(arr);
 }

 public static void findLeadersInAnArrayBruteForce(int arr[])
 {
  System.out.println("Finding leaders in an array using brute force : ");
  for (int i = 0; i < arr.length; i++) {
   boolean isLeader=true;
   for (int j = i+1; j < arr.length; j++) {
    if(arr[i] <= arr[j])
    { 
     isLeader=false;
     break;
    }    
   }
   if(isLeader)
    System.out.print(arr[i]+" ");
  }
 }

 public static void findLeadersInAnArray(int arr[])
 {
  System.out.println("Finding leaders in an array : ");
  int rightMax=arr[arr.length-1];
  // Rightmost will always be a leader
  System.out.print(rightMax+" ");
  for (int i = arr.length-2; i>=0; i--) {
   if(arr[i] > rightMax)
   {
    rightMax=arr[i];
    System.out.print(" "+rightMax);
   }
  }
 }

}

当你运行上面的程序时，你会得到以下输出：

Finding leaders in an array using brute force
99 90 
==================
Finding leaders in an array : 
90  99