+-
PAT_甲级_1057 Stack
首页 专栏 c++ 文章详情
0

PAT_甲级_1057 Stack

乔梓鑫 发布于 2 月 28 日

题目大意

现有一个栈,对其进行执行N次基本操作,该操作有三种类型,分别是Pop,Push和PeekMedian,代表了出栈,入栈和获取栈中元素的中位数,要求按照每一次输入的指令进行相应的输出

算法思路

这里最为复杂的就是实时的获取栈中的中位数,使用拷贝到数组排序或者set集合都会超时,这里借助分块的思想来完成实时获取中位数,除了使用栈st来进行入栈和出栈的基本操作之外,还需要使用block数组和table数字分别保存每一块包含的数字个数和每一个数字出现的次数,第i块(i>=0)保存的数字范围是[iblockSize,(i+1)blockSize-1],那么求解栈的中位数的方法如下:

1、获取中位数的位置k=st.size()/2+st.size()%2; 2、使用sum表示当前累计的数字的个数 3、查找第k大的数字所在的块号i,第一个使得sum+block[i]>=k成立的就是第k大的数字所在的块号 4、查找第k大的数字在第i号块中的对应数字num,第i号块的第一个数字为i blockSize,让num=iblockSize,然后遍历num数字,只要sum+table[num]==k,就说明当前的num就是第k大的数字。

提交结果

AC代码

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
#include <cstring>

using namespace std;

int table[100010];
stack<int> st;

void push(int block[],int x){
    st.push(x);
    ++table[x];
    int blockSize = (int)sqrt(100001*1.0);
    ++block[x/blockSize];
}

int pop(int block[]){
    int x = st.top();
    st.pop();
    --table[x];
    int blockSize = (int)sqrt(100001*1.0);
    --block[x/blockSize];
    return x;
}

int getMedian(const int block[]){
    // 获取中位数的位置
    int k = st.size()/2+st.size()%2;
    // 累计当前已经出现过的数字个数
    int sum = 0;
    int blockSize = (int)sqrt(100001*1.0);
    // 查找第一个使得sum+block[i]>=k的块号i
    int i;
    for(i=0;i<blockSize;++i){
        if(sum+block[i]<k){
            sum += block[i];
        }else{
            break;
        }
    }
    // 第k大的数字在第i块中
    int num;// 保存当前遍历的数字
    int start = i*blockSize;
    int end = (i+1)*blockSize;
    for(num=start;num<end;++num){
        if(sum+table[num]<k){
            sum += table[num];
        }else{
            // 当前num就是第k大的数字
            break;
        }
    }
    return num;
}

int main() {
    int blockSize = (int)sqrt(100001*1.0);
    int block[blockSize];
    memset(block,0,sizeof(block));
    int n;
    scanf("%d",&n);
    string str;
    int num;
    for(int i=0;i<n;++i){
        cin>>str;
        if(str=="Pop"){
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",pop(block));
            }
        }else if(str=="Push"){
            cin>>num;
            push(block,num);
        }else{
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",getMedian(block));
            }
        }
    }
    return 0;
}

c++ 数据结构和算法
阅读 25 发布于 2 月 28 日
收藏
分享
本作品系原创, 采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
PAT题解
关注专栏
avatar
乔梓鑫

主要分享个人学习经验和心得

468 声望
5 粉丝
关注作者
0 条评论
得票 时间
提交评论
avatar
乔梓鑫

主要分享个人学习经验和心得

468 声望
5 粉丝
关注作者
宣传栏
目录

题目大意

现有一个栈,对其进行执行N次基本操作,该操作有三种类型,分别是Pop,Push和PeekMedian,代表了出栈,入栈和获取栈中元素的中位数,要求按照每一次输入的指令进行相应的输出

算法思路

这里最为复杂的就是实时的获取栈中的中位数,使用拷贝到数组排序或者set集合都会超时,这里借助分块的思想来完成实时获取中位数,除了使用栈st来进行入栈和出栈的基本操作之外,还需要使用block数组和table数字分别保存每一块包含的数字个数和每一个数字出现的次数,第i块(i>=0)保存的数字范围是[iblockSize,(i+1)blockSize-1],那么求解栈的中位数的方法如下:

1、获取中位数的位置k=st.size()/2+st.size()%2; 2、使用sum表示当前累计的数字的个数 3、查找第k大的数字所在的块号i,第一个使得sum+block[i]>=k成立的就是第k大的数字所在的块号 4、查找第k大的数字在第i号块中的对应数字num,第i号块的第一个数字为i blockSize,让num=iblockSize,然后遍历num数字,只要sum+table[num]==k,就说明当前的num就是第k大的数字。

提交结果

AC代码

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
#include <cstring>

using namespace std;

int table[100010];
stack<int> st;

void push(int block[],int x){
    st.push(x);
    ++table[x];
    int blockSize = (int)sqrt(100001*1.0);
    ++block[x/blockSize];
}

int pop(int block[]){
    int x = st.top();
    st.pop();
    --table[x];
    int blockSize = (int)sqrt(100001*1.0);
    --block[x/blockSize];
    return x;
}

int getMedian(const int block[]){
    // 获取中位数的位置
    int k = st.size()/2+st.size()%2;
    // 累计当前已经出现过的数字个数
    int sum = 0;
    int blockSize = (int)sqrt(100001*1.0);
    // 查找第一个使得sum+block[i]>=k的块号i
    int i;
    for(i=0;i<blockSize;++i){
        if(sum+block[i]<k){
            sum += block[i];
        }else{
            break;
        }
    }
    // 第k大的数字在第i块中
    int num;// 保存当前遍历的数字
    int start = i*blockSize;
    int end = (i+1)*blockSize;
    for(num=start;num<end;++num){
        if(sum+table[num]<k){
            sum += table[num];
        }else{
            // 当前num就是第k大的数字
            break;
        }
    }
    return num;
}

int main() {
    int blockSize = (int)sqrt(100001*1.0);
    int block[blockSize];
    memset(block,0,sizeof(block));
    int n;
    scanf("%d",&n);
    string str;
    int num;
    for(int i=0;i<n;++i){
        cin>>str;
        if(str=="Pop"){
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",pop(block));
            }
        }else if(str=="Push"){
            cin>>num;
            push(block,num);
        }else{
            if(st.empty()){
                printf("Invalid\n");
            }else{
                printf("%d\n",getMedian(block));
            }
        }
    }
    return 0;
}