Recherche de la majorité (leader) à l'aide d'un tableau implémentation d'une pile

Question

J'essaie de trouver la majorité ou le leader, dans une pile qui n'est pas triée, et j'ai des problèmes avec mes tos (variable de début de pile) . Ci-dessous est mon code avec principal inclus. La majorité d'un tableau ou d'une pile est un élément qui apparaît dans le tableau plus de la moitié du temps (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)); 

} 

Lorsque le problème se pose est dans le chef de file, et les méthodes isLeader, après l'appel initial de isLeader, tos est renvoyée comme tos = -1 comme cela est démontré de ma sortie ci-dessous.

Sortie:

leader 5 
tos 8 
after function tos -1 
-1 

Mon intention est après chaque appel à isLeader() si elle est fausse est retourné, je veux pop la variable tos du haut et appelez isLeader() une fois de plus avec la nouvelle pile plus petite .

Toute aide serait vraiment appréciée, et j'espère que tout le monde va bien!

Merci

Answer 1

je personnellement ajouter une méthode public Integer leader() à votre ArrayStack qui retourne le leader ou null de la pile si la pile n'a pas de leader:

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

fonction Votre isLeader pourrait alors être réécrite à:

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

Cette approche est beaucoup plus propre car elle ne modifie pas ou n'exige aucun interne de votre ArrayStack en dehors de la classe elle-même.

Answer 2

j'ai pu le faire fonctionner en suivant aussi un currSize de la pile pour passer à la fonction isLeader. J'ai l'impression de compliquer les choses, si quelqu'un a une solution plus simple et souhaite la partager, je serais ouvert à cela. Voici mon code si quelqu'un est intéressé.

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