PTA题---求两个有序序列中位数所体现的思想。

---恢复内容开始---

  近日,在做PTA题目时,遇到了一个这样的题,困扰了很久。题目如下:已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,

即第⌊(N+1)/2⌋个数(A​0​​为第1个数)。输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。

  首先,分析题可知:该题中的序列是一个升序

的序列(可能存在连续几个相等数的序列),要求这两个序列的并集,可以使用两个顺序表实现,这两个顺序表所需要的操作是:构造函数、插入函数(用于求集)、析构函数(不需要)、求中位数(因为对象无法访问其私有成员)、再者就是求并集的函数(是本文的重点,稍后奉上)。其次,在三行中输入数,我在N值取法还存在很大疑问,也致使本题始终得不到完全正确的结果, 下次重点分析这个问题。

  求两个序列的并集,会想到的是,遍历其中一个顺序表,将另外一个顺序表一次插入到该顺序表中。注:连个序列中可能分别存在相同的元素,求并是指,将不同的元素插入。下面具体分析一下这问题。

该函数可以使用顺序表作为函数参数的。一个顺序表调用该函数,另外一个作为函数参数,传入进去。

void Seqlist::Union(Seqlist L){
//定义两个变量去遍历两个顺序表
int q = 0;
int w = 0;
//循环结束的标志是遍历完两个顺序表,注意的是q在插入w后其长度会变,而w应该不变
while(q <= length && w < L.length){
//当前data[q] < L.data[w]的话,q++,w保持不变。说明w中的数更大,应该插在后面。
if(data[q] < L.data[w])
q++;
else if(data[q] == L.data[w])
{
q++;
w++;
}
//当data[q]<L.data[w],执行插入
else
insert(q, L.data[w]);
}
//当第一个顺序表遍历完成,而第二个未循环完,将第二个循序表的元素全部插入到第一个循序表中
for( w; w < L.length; w++){
data[q-1] = L.data[w];
q++;
length++;
}
}

上面的比较过程是一个完成的过程,如下面两个序列1 3 5 7 9、 2 3 4 5 6. 首先1 大于 2, 不执行插入,第一个循环表往下,到了3,3相等,不变。接着,4小于5 则执行插入。往后依次类推。

  另附本题的完整答案:

#include<iostream>
using namespace std;
//定义最大连个数列的最大值
const int MaxSize = 100; class Seqlist{
public:
Seqlist(){length = 0;}
Seqlist(int a[], int n);
~Seqlist(){}
void insert(int i, int x);
void Union(Seqlist L2);
void GetMidNum();
private:
int length;
int data[MaxSize];
};
Seqlist::Seqlist(int a[], int n){
for(int i = 0; i < n; i++)
data[i] = a[i];
length = n;
}
void Seqlist::insert(int i, int x){
for(int j = length; j > i; j--){
data[j] = data[j - 1];
}
data[i] = x;
length++;
}
void Seqlist::GetMidNum(){
cout << data[(length - 1) / 2] << endl;
}
void Seqlist::Union(Seqlist L){
int q = 0;
int w = 0;
while(q <= length && w < L.length){
if(data[q] < L.data[w])
q++;
else if(data[q] == L.data[w])
{
q++;
w++;
}
else
insert(q, L.data[w]);
}
for( w; w < L.length; w++){
data[q-1] = L.data[w];
q++;
length++;
}
}
int main(){ int a[MaxSize] = {0};
int b[MaxSize] = {0};
int m ;
cin >> m;
int n = 0;
while(n < 2){
int k = 0;
while(k < m){
if(n == 0)
cin >> a[k];
else
cin >> b[k];
k++;
}
n++;
}
Seqlist L1(a, m);
Seqlist L2(b, m);
L1.Union(L2);
L1.GetMidNum();
return 0;
}

  但是

 

---恢复内容结束---

  近日,在做PTA题目时,遇到了一个这样的题,困扰了很久。题目如下:已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,

即第⌊(N+1)/2⌋个数(A​0​​为第1个数)。输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。

  首先,分析题可知:该题中的序列是一个升序

的序列(可能存在连续几个相等数的序列),要求这两个序列的并集,可以使用两个顺序表实现,这两个顺序表所需要的操作是:构造函数、插入函数(用于求集)、析构函数(不需要)、求中位数(因为对象无法访问其私有成员)、再者就是求并集的函数(是本文的重点,稍后奉上)。其次,在三行中输入数,我在N值取法还存在很大疑问,也致使本题始终得不到完全正确的结果, 下次重点分析这个问题。

  求两个序列的并集,会想到的是,遍历其中一个顺序表,将另外一个顺序表一次插入到该顺序表中。注:连个序列中可能分别存在相同的元素,求并是指,将不同的元素插入。下面具体分析一下这问题。

该函数可以使用顺序表作为函数参数的。一个顺序表调用该函数,另外一个作为函数参数,传入进去。

void Seqlist::Union(Seqlist L){
//定义两个变量去遍历两个顺序表
int q = 0;
int w = 0;
//循环结束的标志是遍历完两个顺序表,注意的是q在插入w后其长度会变,而w应该不变
while(q <= length && w < L.length){
//当前data[q] < L.data[w]的话,q++,w保持不变。说明w中的数更大,应该插在后面。
if(data[q] < L.data[w])
q++;
else if(data[q] == L.data[w])
{
q++;
w++;
}
//当data[q]<L.data[w],执行插入
else
insert(q, L.data[w]);
}
//当第一个顺序表遍历完成,而第二个未循环完,将第二个循序表的元素全部插入到第一个循序表中
for( w; w < L.length; w++){
data[q-1] = L.data[w];
q++;
length++;
}
}

上面的比较过程是一个完成的过程,如下面两个序列1 3 5 7 9、 2 3 4 5 6. 首先1 大于 2, 不执行插入,第一个循环表往下,到了3,3相等,不变。接着,4小于5 则执行插入。往后依次类推。

  另附本题的完整答案:

#include<iostream>
using namespace std;
//定义最大连个数列的最大值
const int MaxSize = 100; class Seqlist{
public:
Seqlist(){length = 0;}
Seqlist(int a[], int n);
~Seqlist(){}
void insert(int i, int x);
void Union(Seqlist L2);
void GetMidNum();
private:
int length;
int data[MaxSize];
};
Seqlist::Seqlist(int a[], int n){
for(int i = 0; i < n; i++)
data[i] = a[i];
length = n;
}
void Seqlist::insert(int i, int x){
for(int j = length; j > i; j--){
data[j] = data[j - 1];
}
data[i] = x;
length++;
}
void Seqlist::GetMidNum(){
cout << data[(length - 1) / 2] << endl;
}
void Seqlist::Union(Seqlist L){
int q = 0;
int w = 0;
while(q <= length && w < L.length){
if(data[q] < L.data[w])
q++;
else if(data[q] == L.data[w])
{
q++;
w++;
}
else
insert(q, L.data[w]);
}
for( w; w < L.length; w++){
data[q-1] = L.data[w];
q++;
length++;
}
}
int main(){ int a[MaxSize] = {0};
int b[MaxSize] = {0};
int m ;
cin >> m;
int n = 0;
while(n < 2){
int k = 0;
while(k < m){
if(n == 0)
cin >> a[k];
else
cin >> b[k];
k++;
}
n++;
}
Seqlist L1(a, m);
Seqlist L2(b, m);
L1.Union(L2);
L1.GetMidNum();
return 0;
}

  但是

 

上一篇:【easyui】Tab的tools按钮刷新当前tab


下一篇:SLA服务可用性怎么达到?