使用堆栈的数组实现寻找多数（领导者）

Question

我试图找到大多数人或领导者，在一个没有排序的堆栈中，并且我遇到了问题（堆栈变量的顶部） 。以下是我主要包含的代码。数组或堆栈的大部分是出现在数组中超过一半时间的任何元素（arrSize/2）。

public class findLeader { 

static class ArrayStack{ 
    private int[] stackArr; 
    private int tos;//top of stack 

    public ArrayStack(){ 
     stackArr = new int[10]; 
     tos = -1; 
    } 

    public ArrayStack(int size){ 
     stackArr = new int[size]; 
     tos = -1; 
    } 

    public ArrayStack(int[] arr, int tos){ 
     stackArr = arr; 
     this.tos = tos; 
    } 

    public boolean isEmpty(){ 
     return(tos == -1); 
    } 

    public int peek(){ 
     if(isEmpty()){ 
      return -999; 
     } 
     return stackArr[tos]; 
    } 

    public void push(int x){ 
     if(tos == stackArr.length - 1){ 
      return; 
     } 
     stackArr[++tos] = x; 
    } 

    public int pop(){ 
     if(isEmpty()){ 
      return -999; 
     } 
     int popValue = stackArr[tos]; 
     stackArr[tos] = 0; 
     --tos; 
     return popValue; 
    } 

    public void print(){ 
     if(isEmpty()){ 
      return; 
     } 
     for(int i = 0; i <= tos; ++i){ 
      System.out.print(stackArr[i] + " "); 
     } 
     System.out.println(); 
    } 

} 

public static int leader(ArrayStack myStack){ 

    int initSize = myStack.tos + 1; //gets initial size of stack. 
    int leader; //initialize leader or majority. 

    while(!myStack.isEmpty()){ 
     leader = myStack.peek();//set first leader variable to the element at the tos. 
     System.out.println("leader " + leader); //just for debugging 
     System.out.println("tos " + myStack.tos); //debugging 
     //System.out.println(isLeader(myStack, initSize, leader)); //debugging 
     if(isLeader(myStack, initSize, leader)){  
      return 1; 
     } 
     else{ 
      myStack.pop(); 
     } 
     System.out.println("after function tos " + myStack.tos); //debugging   
    } 

    return -1; 
} 

public static boolean isLeader(ArrayStack myStack, int initSize, int leader){ 
    ArrayStack as = myStack; 
    int count = 0; 

    while(!as.isEmpty()){ 
     if(as.peek() == leader){ 
      as.pop(); 
      ++count; 
     } 
     else{ 
      as.pop(); 
     } 
    } 
    //System.out.println(count); 
    if(count > initSize/2) 
     return true; 
    else{ 
     return false; 
    } 
} 

public static void main(String[] args) { 
    int[] arr = {2, 5, 6, 2, 8, 2, 8, 2, 2}; 

    ArrayStack stack = new ArrayStack(); 

    stack.push(5); 
    stack.push(2); 
    stack.push(6); 
    stack.push(2); 
    stack.push(8); 
    stack.push(2); 
    stack.push(2); 
    stack.push(2); 
    stack.push(5); 

    System.out.println(leader(stack)); 

} 

当出现问题是在领导者，isLeader方法，isLeader的初始呼叫后，TOS被返回TOS = -1作为从我下面的输出展示。

输出：

leader 5 
tos 8 
after function tos -1 
-1 

我的意图是每次调用isLeader（）如果返回false，我想从顶部用新的更小堆栈弹出TOS变量，并调用isLeader（）一次后。

任何帮助真的会被赞赏，我希望每个人都很好！

谢谢

Answer 1

我个人添加了一个方法public Integer leader()您ArrayStack返回堆栈的领导或null如果栈没有领导者：

public Integer leader() { 
    final Map<Integer, Integer> counts = new HashMap<>(); 
    final int neededLeaderCount = ((tos + 1)/2) + 1; 
    for (int i = 0; i <= tos; ++i) { 
     int currentElementCount = counts.getOrDefault(stackArr[i], 0) + 1; 
     if (currentElementCount >= neededLeaderCount) { 
      return stackArr[i]; 
     } 
     counts.put(stackArr[i], currentElementCount); 
    } 
    return null; 
} 

你isLeader功能然后可以改写为：

public static boolean isLeader(ArrayStack myStack, int leader) { 
    // use Objects.equals as myStack.leader() may be null 
    return Objects.equals(myStack.leader(), leader); 
} 

这种方法更加清洁，因为它不会修改或要求您的内部任何内容ArrayStack以外的类本身。

Answer 2

我能得到它也跟踪堆栈的currSize工作传递给isLeader功能。我觉得我很复杂，如果任何人有一个更简单的解决方案，并希望分享它，我会打开它。如果有人感兴趣，以下是我的代码。

public static int leader(ArrayStack myStack){ 
    int currSize = myStack.tos; 
    int initSize = myStack.tos + 1; //gets initial size of stack. 
    int leader; //initialize leader or majority. 

    while(!myStack.isEmpty()){ 
     leader = myStack.peek();//set first leader variable to the element at the tos. 
     System.out.println("leader " + leader); //just for debugging 
     System.out.println("tos " + myStack.tos); //debugging 
     //System.out.println(isLeader(myStack, initSize, leader)); //debugging 
     if(isLeader(myStack, initSize, leader, currSize)){  
      return 1; 
     } 
     else{ 
      --currSize; 
      myStack.pop(); 
     } 
     System.out.println("after function tos " + myStack.tos); //debugging   
    } 

    return -1; 
} 

public static boolean isLeader(ArrayStack myStack, int initSize, int leader, int currSize){ 
    ArrayStack as = myStack; 
    int count = 0; 


    while(as.tos > -1){ 
     if(as.peek() == leader){ 
      --as.tos; //Just move tos pointer down stack rather than popping 
         //to maintain original stack. 
      ++count; 
     } 
     else{ 
      --as.tos; 
     } 
    } 

    if(count > initSize/2) 
     return true; 
    else{ 
     as.tos = currSize;//reset the tos pointer back to the currSize of 
          //stack. 
     return false; 
    } 
}