[第二轮] 3/4-3/10 CareerCup 3.6

EchoMemory 发表于 2013-3-4 12:34
ok..my solution is based in the description of the problem, where "You may use additional stacks"  ...

one additional stack: other, is enough. This additional stack holds all the sorted items.
while(!input.isEmpty)
    Use tmp to store the input.pop
    while(!other.isEmpty & other.peek is greater then tmp)
        input.push(other.pop)
    other.push(tmp)
return other

ryancooper 发表于 2013-3-4 14:21
If I can be allowed to use one additional variable, then I can reduce two additional stacks to jus ...

Yes, I understand your solution. Thx for reminder, I edited again.

lty900301 发表于 2013-3-4 15:12
one additional stack: other, is enough. This additional stack holds all the sorted items.
while( ...

I see...that's right, too.

https://github.com/longwei/Algo/ ... h3/SortedStack.java
Note:
1. pop arbitrary element from Stack1, and push into Stack2, and then pop S2 back to S1. the order is stable. which give us a double-linked list data structure.
2. as a result, we could pop unsorted stack, and insert it into the right position in the sorted stack

用了两个stack， 思想跟答案一致
c++ implementation

https://github.com/StanleyLee/CareerCup/blob/master/3_6.cpp

https://gist.github.com/flatlight/5126811
在另一个栈中做插入排序

https://gist.github.com/ThunderXu/5127102
Take the idea from QuickSort, use recursion to solve the problem, when there are only 2 elements, it is easy to sort them only by stacks. One thing to pay attention to is a stack can not be copied to another just by poping it and pushing another, in that situation the elements of these two stacks will be reversed.

这个题对时间复杂度有要求吗？ 我能想到的最好办法n平方可以解决，三个stack的办法

https://github.com/1094401996/Ca ... AscendingStack.java

两个堆栈来回倒。。。。。

同两个stack
https://gist.github.com/chrislukkk/5167080