java - 使用堆栈的数组实现查找多数(领导者)

Question

我试图在未排序的堆栈中找到多数或领导者，但我的 tos(堆栈顶部变量)遇到了问题。下面是我的代码，其中包含主要内容。数组或堆栈的大部分是在数组中出现次数超过一半的元素 (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

我个人会向您的 ArrayStack 添加一个方法 public Integerleader()，该方法返回堆栈的领导者或 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 的任何内部结构。