【考研·数据结构】408真题 (2011年42题) 的三种解法】_2011年计…(数据结构考研必背知识点)
2011 找出中位数
一个长度为 l(l1)的升序序列 s找出两个序列 a和 b的中位数。要求:
- 给出算法的基本设计思想。根据设计思想关键之处给出注释说明你所设计算法的时间复杂度和空间复杂度。
暴力解法
- 快排排序然后输出
快排思想然后交换两个元素。最后两指针相遇且将最后一个位置与基准元素 记录数组
新建一个数组然后输出中间位置 计数器法
用一个计数器表示当前元素是第几小输出第n个元素
代码实现
//快排
#include<iostream>
using namespace std;
void qsort(int arr[], int l, int r,int n)
{
if (l > r) // 当左指针大于等于右指针时退出递归
return;
int pivot;
int i l, j r;
pivot arr[l]; // 以左端点为枢轴元素
while (i < j)
{
while (i < j && arr[j] > pivot)
j--; // 找到右边小于等于枢轴的元素
while (i < j && arr[i] < pivot)
i; // 找到左边大于枢轴的元素
if (i < j)
swap(arr[i], arr[j]); // 交换左边大于枢轴和右边小于等于枢轴的元素
}
swap(arr[l], arr[i]); // 将枢轴归位
qsort(arr, l, i - 1,i-l); // 对左半部分递归进行快速排序
qsort(arr, i 1, r,r-i); // 对右半部分递归进行快速排序
}
void ans(int arr[], int arr1[], int n)
{
int* arr2 new int[2*n];
for (int i 0; i < n; i)
{
arr2[i] arr[i]; // 将 arr 复制到 arr2
arr2[n i] arr1[i]; // 将 arr1 复制到 arr2
}
qsort(arr2, 0, 2*n - 1, 2*n); // 对 arr2 进行快速排序
cout << arr2[n- 1]; // 输出 arr2 的第 n 大元素
}
int main()
{
int n;
cin >> n;
int* arr new int[n];
int* arr1 new int[n];
for (int i 0; i < n; i)
{
cin >> arr[i]; // 输入 arr 数组
}
for (int i 0; i < n; i)
{
cin >> arr1[i]; // 输入 arr1 数组
}
ans(arr, arr1, n); // 调用 ans 函数输出结果
// 记得释放内存
delete[] arr;
delete[] arr1;
}
//输入格式
//6
//1 2 3 4 5 6
//2 3 4 5 6 7
//输出格式
//3
//记录数组
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int* arr new int[n]; // 定义一个
长度为 n 的整型数组 arr
int* arr1 new int[n]; // 定义一个长度为 n 的整型数组 arr1
int* arr2 new int[2 * n]; // 定义一个长度为 2n 的整型数组 arr2
int p 0; // 定义指针 p初始值为 0
int k 0; // 定义指针 k初始值为 0
/* 输入数组 arr 和 arr1 */
for (int i 0; i < n; i)
{
cin >> arr[i];
}
for (int i 0; i < n; i)
{
cin >> arr1[i];
}
/* 归并排序 */
for (int i 0; i < 2 * n; i)
{
if (arr[p] < arr1[k]) // 如果 arr[p] 小于 arr1[k]
{
arr2[i] arr[p]; // 则将 arr[p] 存到 arr2[i] 中并将指针 p 加一
if (p n) // 如果 p 已经到达数组 arr 的末尾
{
p n - 1; // 则将指针 p 设为数组 arr 的最后一个元素的下标
continue; // 继续循环
}
}
else // 否则arr1[k] 更小
arr2[i] arr1[k]; // 则将 arr1[k] 存到 arr2[i] 中并将指针 k 加一
}
cout << arr2[n - 1]; // 输出 arr2 的第 n 大元素
/* 释放内存 */
delete[] arr;
delete[] arr1;
delete[] arr2;
}
//计数器法
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int* arr new int[n]; // 动态分配长度为 n 的整型数组 arr
int* arr1 new int[n]; // 动态分配长度为 n 的整型数组 arr1
int sum 0; // 记录比较次数的变量 sum初始值为 0
int p 0; // 定义指针 p初始值为 0
int k 0; // 定义指针 k初始值为 0
/* 输入数组 arr 和 arr1 */
for (int i 0; i < n; i)
{
cin >> arr[i];
}
for (int i 0; i < n; i)
{
cin >> arr1[i];
}
/* 执行归并排序 */
for (int i 1; i < n; i)
{
if (arr[p] < arr1[k]) // 如果 arr[p] 小于 arr1[k]
{
p; // 将指针 p 加一
sum; // 比较次数加一
}
else // 否则arr1[k] 更小
{
k; // 将指针 k 加一
sum; // 比较次数加一
}
}
/* 输出第 n 小的数 */
cout << min(arr[p], arr1[k]);
/* 释放动态分配的内存 */
delete[] arr;
delete[] arr1;
return 0; // 返回程序正常结束
}
评论