找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

12
返回列表 发新帖
楼主: uuuouou
收起左侧

[资源分享] 13: Sort A Stack

[复制链接]

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
发表于 10-6-2015 08:18 AM | 显示全部楼层
  1. class Solution {
  2. public:
  3.     void merge(stack<int>& s, int stride) {
  4.         int sz = s.size();
  5.         stack<int> tmp, res;
  6.         for(int start = 0; start < sz; start += stride) {
  7.             int end = min(start + stride - 1, sz - 1);
  8.             int mid = min(start + (stride >> 1) - 1, sz - 1);
  9.             int t = 0, f = start, i = mid + 1;
  10.             for(f = start; f <= mid; f++) {
  11.                 res.push(s.top());
  12.                 s.pop();
  13.             }   
  14.             for(f = start; f <= mid; f++) {
  15.                 tmp.push(res.top());
  16.                 res.pop();
  17.             }   
  18.             for(i = start, f = mid + 1; i <= mid && f <= end;) {
  19.                 if(s.top() >= tmp.top()) {
  20.                     res.push(s.top());
  21.                     s.pop();
  22.                     f++;
  23.                 }   
  24.                 else {
  25.                     res.push(tmp.top());
  26.                     tmp.pop();
  27.                     i++;
  28.                 }   
  29.             }   
  30.             while(i <= mid) {
  31.                 res.push(tmp.top());
  32.                 tmp.pop();
  33.                 i++;
  34.             }   
  35.             while(f <= end) {
  36.                 res.push(s.top());
  37.                 s.pop();
  38.                 f++;
  39.             }   
  40.         }   
  41.         while(!res.empty()) {
  42.             s.push(res.top());
  43.             res.pop();
  44.         }   
  45.     }   
  46.     stack<int> sortStack(stack<int>& s) {
  47.         int sz = s.size();
  48.         int stride = 2;
  49.         for(stride = 2; stride < sz; stride <<= 1) {
  50.             merge(s, stride);
  51.         }   
  52.         merge(s, stride);
  53.         return s;
  54.     }   
  55. };
复制代码
回复 支持 反对

使用道具 举报

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
发表于 10-6-2015 08:19 AM | 显示全部楼层
uuuouou 发表于 10-6-2015 06:58 AM
可不可以给个代码看看呀

用了两个栈。。不知道题意里的one additional stack是算上输入和输出之外还能另外有一个栈的意思吗
回复 支持 反对

使用道具 举报

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

本版积分规则

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