博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
PAT-1057 Stack (树状数组 + 二分查找)
阅读量:5318 次
发布时间:2019-06-14

本文共 3466 字,大约阅读时间需要 11 分钟。

1057. Stack

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 105). Then N lines follow, each contains a command in one of the following 3 formats:

Push key
Pop
PeekMedian

where key is a positive integer no more than 105.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print "Invalid" instead.

Sample Input:
17PopPeekMedianPush 3PeekMedianPush 2PeekMedianPush 1PeekMedianPopPopPush 5Push 4PeekMedianPopPopPopPop
Sample Output:
InvalidInvalid322124453Invalid

题目大意:要求实现一个栈,除了基础的push和pop操作外,还要拥有查找中间数的操作 (PeekMedian),即n个栈中元素在排序后,该元素的大小排行为 (n+1)/2。因为可能存在大量的查找中间数的操作,所以必须找到快速的解决方法。

主要思想:解此题的过程可谓是一波三折。开始的想法很天真,在每次需要PeekMedian的时候,将栈中元素全部拷贝到一个辅助数组,然后对该数组进行排序,很容易找到中间值,时间复杂度为 O((n^2) lgn),很显然最后超时了。

由于题目说明数据范围为 1~100000,想到了用一个count[]数组来储存每一个数在栈中的个数,然后每一次通过遍历数组累积,当 S[i] = count[1] + count[2] + ... + count[i] >= (n+1)/2 的时候则找到中间值i,时间复杂度为 O(n^2)。

这样显然还会超时,在这个想法的基础上利用树状数组,这种数据结构可以很快的得出前 i 项和,从而可以利用二分查找来找到中间数。于是,push和pop操作时间复杂度为 O(lgn),PeekMedian的复杂度为 O(n (lgn)^2),问题解决。

#include 
#include
#include
#include
#define MAXN 100005using namespace std;int stack[MAXN]; //array of stackint c[MAXN]; //BITint n = 0;/* functions of Binary Index Tree (BIT) */int lowbit(int x) { return x & (-x);}int get_sum(int x) { int sum = 0; for (int i = x; i > 0; i -= lowbit(i)) sum += c[i]; return sum;}void update(int x, int t) { for (int i = x; i <= MAXN; i += lowbit(i)) c[i] += t;}/* operations of stack */bool isEmpty() { return n == 0;}void push(int key) { stack[n++] = key; update(key, 1);}int pop() { int k = stack[--n]; update(k, -1); return k;}int peek_median() { int lo = 1, hi = MAXN; int median = (n + 1) / 2; //use the binary search while (lo <= hi) { int mid = (lo + hi) / 2; if (median > get_sum(mid)) lo = mid + 1; else // median <= get_sum(mid) hi = mid - 1; } return lo;}int main(void) { int m; char comment[11]; scanf("%d", &m); getchar(); for (int i = 0; i < m; i++) { gets(comment); if (comment[1] == 'u') { //push int key = atoi(comment+5); push(key); } else if (comment[1] == 'o') { //pop if(isEmpty()) { printf("Invalid\n"); continue; } int t = pop(); printf("%d\n", t); } else { //peek median if (isEmpty()) { printf("Invalid\n"); continue; } int m = peek_median(); printf("%d\n", m); } } return 0;}

转载于:https://www.cnblogs.com/zhayujie/p/7534852.html

你可能感兴趣的文章
《Algorithms》第6章:Dynamic Programming 学习笔记
查看>>
1168: mxh对lfx的询问(前缀和+素数表)
查看>>
python中time类型,datetime类型的关系与互相转换
查看>>
【php】基础学习4
查看>>
递归神经网络(Recursive Neural Network, RNN)
查看>>
给wxPython事件处理函数传递参数
查看>>
csv文件批量导入数据到sqlite。
查看>>
实验三-有穷自动机的构造和识别
查看>>
Jdk在window环境下的安装与配置详解
查看>>
C# 两个窗体中相互切换的方法
查看>>
Individual Project - Word frequency program
查看>>
luogu P3924 康娜的线段树
查看>>
JAVA入门[18]-JdbcTemplate简单实例
查看>>
Eclipse 插件安装报错问题(已解决)
查看>>
String常见面试题及与StringBuffer区别
查看>>
HDU 4557 非诚勿扰(Treap找后继)
查看>>
嘴不笨来试试??太好玩儿了,看看谁厉害?
查看>>
【nginx运维基础(7)】常用PHP开源程序的NginxRewrite示例
查看>>
C 可变长参数运用-----编写Lua的通用调用函数
查看>>
PHP 各个框架的优缺点(超详细)
查看>>