使用堆棧的數組實現尋找多數（領導者）

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; 
    } 
}