我们需要打印数组中存在的所有leaders。如果元素大于元素的右侧,则元素是领导者。 例如:
arr[]={14, 12, 70, 15, 99, 65, 21, 90} Here 99 and 90 are leader elements
使用两个循环。外循环迭代数组元素,内循环检查数组的正确元素。如果当前元素大于右侧元素,则它是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