gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-30 06:28:30 27 4
gpt4 key购买 nike

我试图在未排序的堆栈中找到多数或领导者,但我的 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() 。

任何帮助都将不胜感激,希望每个人都一切顺利!

谢谢

最佳答案

我个人会向您的 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 的任何内部结构。

关于java - 使用堆栈的数组实现查找多数(领导者),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46611829/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com