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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop |
Sample Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Invalid Invalid 3 2 2 1 2 4 4 5 3 Invalid |
一道很有意思的题，题目的难点在于 PeekMedian 的实现，如果直接去遍历，则一定会超时，而且栈中的数可能一直在变化，采用 BFPRT 取中值在复制数组时会付出更大的时间开销。考虑到，“where key is a positive integer no more than 105”，可以考虑直接开一个数组来记录某个 key 是否存在以获取中值（第 k 个存在的数即为中值，若采用0与1来区分，那么数组元素直接累加至 k 时的下标值即为中值），但是也会超时。这里就用了树状数组以提升累加运算的效率，同时采用二分查找来确定中值。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#include<stdio.h> #include<stdlib.h> #define max_val 100001 typedef struct stack_ { int size; int capacity; int top; int *data; } stack; int tree[max_val]; int get(int index) { int sum=0; while(index>0) { sum+=tree[index]; index-=(index&-index); } return sum; } int update(int index,int value,int max) { while(index<=max) { tree[index]+=value; index+=(index&-index); } return 0; } #define is_stack_empty(X) (!((X)->size)) #define ptr_top(X) ((X)->data[(X)->top]) stack *inti_stack(int n) { stack *temp; temp=(stack *)malloc(sizeof(stack)); temp->size=0; temp->capacity=n; temp->top=-1; temp->data=(int *)malloc(n*sizeof(int)); return temp; } int push(stack *s,int data) { if(s->size==s->capacity) { return 1; } (s->top)++; (s->size)++; s->data[s->top]=data; update(data,1,s->capacity); return 0; } int pop(stack *s,int *data) { if(s->size==0) { *data=-1; return 1; } *data=s->data[s->top]; update(*data,-1,s->capacity); (s->size)--; (s->top)--; return 0; } int find(int dest,int begin,int end) { if(begin==end) { return begin; } if(get((begin+end)/2)>=dest) { return find(dest,begin,(begin+end)/2); } else { return find(dest,(begin+end)/2+1,end); } } int peekmedian(stack *s,int *data) { int i,n; if(s->size==0) { *data=-1; return 1; } if(s->size==1) { *data=s->data[0]; return 0; } n=(s->size+1)/2; *data=find(n,1,s->capacity); return 0; } int main() { int n,i,temp,value; stack *s; char command[12],buf[5]; scanf("%d",&n); getchar(); s=inti_stack(max_val); for(i=0;i<n;i++) { gets(command); switch(command[1]) { case 'u': sscanf(command,"%s%d",buf,&temp); push(s,temp); break; case 'o': pop(s,&temp); if(temp==-1) { printf("Invalid\n"); } else { printf("%d\n",temp); } break; case 'e': peekmedian(s,&temp); if(temp==-1) { printf("Invalid\n"); } else { printf("%d\n",temp); } break; } } } |