找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 53|回复: 0

[代码与实例] Lintcode463 Sort Integers solution 题解

10

主题

10

帖子

10

积分

贫民

积分
10
Jenny 发表于 2018-6-13 22:10:00 | 显示全部楼层 |阅读模式
【题目描述】
Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.
给一组整数,按照升序排序,使用选择排序,冒泡排序,插入排序或者任何 O(n2) 的排序算法。

【题目解析】
根据题目提示,可以设想利用另一个stack作为临时储存空间,设定的规则是:
从origin stack中不断pop() element
对于helper stack,如果helper stack peek() < element,则将helper stack中的元素全部转移到origin stack
再将element push()到helper stack中
不断重复上述步骤,直到origin stack isEmpty
最后,所有的元素已经按照descending order排序好(smallest on top),只需将其转移到origin stack,则origin stack即为所需排序
时间复杂度为O(n^2),空间复杂度为O(n)



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表