首页 > 试题广场 >

双栈排序

[编程题]双栈排序

热度指数：16120 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个int[] numbers(C++中为vector&ltint>)，其中第一个元素为栈顶，请编写程序将栈进行升序排列（即最大元素位于栈顶），返回排序后的栈。要求最多使用一个额外的栈存放临时数据，但不得将元素复制到别的数据结构中。并注意这是一个栈，意味着排序过程中只能访问到最后一个元素。

测试样例：

[1,2,3,4,5]

返回：[5,4,3,2,1]

算法知识视频讲解

Python

甲壬

# -*- coding:utf-8 -*-
class TwoStacks:
def twoStacksSort(self, numbers):
# write code here
if not numbers:
return numbers
stack = []
while numbers:
t = numbers.pop()
if not stack or t < stack[-1]:
stack.append(t)
else:
while stack and t >= stack[-1]:
numbers.append(stack.pop())
stack.append(t)

return stack

感觉python用正经的算法去写，反而通不过。

提交结果：运行超时运行时间：6001ms 占用内存：0KB 使用语言：Python 用例通过率：0.00%

发表于 2021-05-17 07:48:20 回复(0)

Python

-201904112354557

# -*- coding:utf-8 -*-
class TwoStacks:
def twoStacksSort(self, numbers):
# write code here
sort_stack = []
while numbers:
if not sort_stack:
sort_stack.append(numbers.pop())
else:
tmp = numbers.pop()
count = 0
while sort_stack and sort_stack[-1] < tmp:
numbers.append(sort_stack.pop())
sort_stack.append(tmp)
return sort_stack

发表于 2020-02-15 03:06:32 回复(0)

Python

微201903010939141

Python代码：

用了一个辅助栈

# -*- coding:utf-8 -*-
class TwoStacks:
    def twoStacksSort(self, numbers):
        # write code here
        #辅助栈nums
        nums=[numbers.pop()]
        #遍历numbers栈顶
        while numbers:
            #若nums为空（因为下面有逆序压入numbers的操作），将numbers栈顶压入nums（因为下面已经逆序压入了）
            if not nums:
                nums.append(numbers.pop())
            else:
                a=numbers.pop()
                b=nums.pop()
                #如果numbers栈顶小于nums栈顶，将其压入nums
                if a<=b:
                    nums.append(b)
                    nums.append(a)
                #栈顶小的话，将其逆序压入numbers
                else:
                    numbers.append(b)
                    numbers.append(a)
        return nums

发表于 2019-03-22 09:48:57 回复(0)

Python

华科平凡

python one line solution:


        return sorted(numbers,reverse=True)

发表于 2017-10-01 20:28:53 回复(1)

Python

啥也没有

# -*- coding:utf-8 -*-
class TwoStacks:
    def twoStacksSort(self, numbers):
        # write code here
        fuzhu = []
        while numbers:
            count = 0
            minnum = float('inf')
            while numbers:
                x = numbers.pop(0)
                count += 1
                if x < minnum:
                    minnum = x
                fuzhu.insert(0,x)
            count1 = 0
            sign = 1
            while count1 != count:
                y = fuzhu.pop(0)
                count1 += 1
                if y == minnum and sign:
                    sign = 0
                    continue
                else:
                    numbers.insert(0,y)
            fuzhu.insert(0,minnum)
        return fuzhu

发表于 2017-05-12 10:38:45 回复(0)

Python

Yannyezixin

思路：

临时变量来存放原栈的栈顶

栈2已经是排好序的了，找到临时变量应该插在栈2中的位置n，把位置n以上的元素出栈到原栈中，插入临时变量

注意：题目的测试结果有问题，变成了最小元素在栈顶

# -*- coding:utf-8 -*-
class TwoStacks:
    def twoStacksSort(self, numbers):
        if not numbers:
            return []

        result = []

        while numbers:
            tmp = numbers.pop()
            while result and result[-1] < tmp:
                numbers.append(result.pop())
            result.append(tmp)
        return result

发表于 2016-08-02 16:21:54 回复(0)