PAT Advanced 1029 Median (25) [two pointers]
题目
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13. Given two increasing sequences of integers, you are asked to find their median.
Input
Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.
Output
For each test case you should output the median of the two given sequences in a line.
Sample Input
4 11 12 13 14
5 9 10 15 16 17
Sample Output
13
题目分析
已知两个有序序列S1,S2,求有序序列S中间位置的元素(S=S1+S2)
解题思路
- 输入S1,S2并合并,打印中间位置元素
- two pointer思想:两个指针,分别指向S1,S2当前元素,比较大小,先将小的合并,并向前移动一位
- 合并时优化
- 1 只要到达中间位置即可打印退出,不需要处理后续数据的合并;
- 2 哨兵简化合并操作
易错点
- S长度分别为偶数和奇数时,中间位置计算为(N1+N2-1)>>1
知识点
- 利用哨兵简化合并操作
- two pointer思想合并两个有序集合为一个有序集合
Code
Code 01(最优、哨兵简化合并、中间位置后数据不处理)
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char * argv[]) {
// 1 输入数据
int N1,N2;
scanf("%d",&N1);
int S1[N1+1]= {0};
for(int i=0; i<N1; i++)scanf("%d",&S1[i]);
scanf("%d",&N2);
int S2[N2+1]= {0};
for(int i=0; i<N2; i++)scanf("%d",&S2[i]);
S1[N1]=S2[N2]=0x7fffffff;// 哨兵
// 2 合并序列--哨兵+若索引到达midpos,直接打印S[midpost],后面的数据不需要处理
int i=0,j=0,index=0,cnt=0,S[N1+N2]= {0};
int midpos = (N1+N2-1)>>1;
while(index<N1+N2) {
if(S1[i]<=S2[j]) S[index++]=S1[i++];
else S[index++]=S2[j++];
if(index-1==midpos) break;
}
printf("%d",S[midpos]);
return 0;
}
Code 02(哨兵简化合并、中间位置后续数据处理)
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char * argv[]) {
// 1 输入数据
int N1,N2;
scanf("%d",&N1);
int S1[N1+1]= {0};
for(int i=0; i<N1; i++)scanf("%d",&S1[i]);
scanf("%d",&N2);
int S2[N2+1]= {0};
for(int i=0; i<N2; i++)scanf("%d",&S2[i]);
S1[N1]=S2[N2]=0x7fffffff;// 哨兵
// 2 合并序列--哨兵
int i=0,j=0,index=0,S[N1+N2]= {0};
while(index<N1+N2) {
if(S1[i]<=S2[j]) {
S[index++]=S1[i++];
} else {
S[index++]=S2[j++];
}
}
printf("%d",S[((N1+N2-1)>>1)]);
return 0;
}
Code 03(无哨兵简化合并、中间位置后续数据处理)
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char * argv[]) {
// 1 输入数据
int N1,N2;
scanf("%d",&N1);
int S1[N1]= {0};
for(int i=0; i<N1; i++)scanf("%d",&S1[i]);
scanf("%d",&N2);
int S2[N2]= {0};
for(int i=0; i<N2; i++)scanf("%d",&S2[i]);
// 2 合并序列
int i=0,j=0,index=0,S[N1+N2]= {0};
while(i<N1&&j<N2) {
if(S1[i]<=S2[j]) {
S[index++]=S1[i++];
} else {
S[index++]=S2[j++];
}
}
while(i<N1)S[index++]=S1[i++];
while(j<N2)S[index++]=S2[j++];
printf("%d",S[((N1+N2-1)>>1)]);
return 0;
}
最新文章
- iOS---FMDB数据升级
- Tomcat报java.lang.OutOfMemoryError: Java heap space错误停止运行如何解决
- WCF 服务调用 QueryRun
- iOS边练边学--NSURLConnection发送HTTP请求以及NSString和NSData的相互转换
- 为mysql在表的某一位置增加一列
- POJ 1944 - Fiber Communications
- SPF详解2
- [LINQ]查询关键字
- ExtJs在disabled和readOnly美学分析
- 【开发必备】今天我们来谈谈Android NDK动态链接库(so文件)的一些见解
- tmux frequently asked questions
- Python函数案例——员工信息管理
- LxmlLinkExtractor类参数解析
- JavaScript 循环语句
- 学习ActiveMQ(五):activemq的五种消息类型和三种监听器类型
- LeetCode--035--搜索插入位置(java)
- Spring boot 使用多个RedisTemplate
- myeclipse中配置spring xml自己主动提示
- 关于dumper和mysqldump的
- centos7下apache2.4反向代理