对堆栈/算法改进空间进行排序的更好方法

Question

我试图找出以下问题的最佳解决方案：给定一个范围为1-5的20个整数的堆栈，对堆栈进行排序，使只有1-4的值保持升序。您一次只能移动一个值。

我实现了一个迭代的

我应该考虑哪一种类型？我应该考虑哪些数据类型？对于给定的问题，最好的可能更坏的情况是什么O（？）？

HashMap<Integer, Integer> map = new HashMap<>();

map.put(1, 0);

map.put(2, 0);

map.put(3, 0);

map.put(4, 0);

int popped;


while(!stack.isEmpty()){

popped = stack.pop();

if(map.containsKey(popped)){

map.put(popped, map.get(popped)+1);

}

}


while (map.get(4)>0){

stack.push(4);

map.put(4, map.get(4)-1);

}


while (map.get(3)>0){

stack.push(3);

map.put(3, map.get(3)-1);

}


while (map.get(2)>0){

stack.push(2);

map.put(2, map.get(2)-1);

}


while (map.get(1)>0){

stack.push(1);

map.put(1, map.get(1)-1);

}

Answer 1

您正在重新创建计数排序算法，该算法在O（n）中运行。

相反，一个< code>HashMap你可以使用一个普通数组。您肯定不需要这种多余的< code > while -循环。