代码实现：
#include
using namespace std;
double findMedianSortedArray(int A[], int n, int B[], int m){//核心思想:一次归并排序过程的模拟
int len = n + m;
int left = -1, right = -1;//right 保存当前循环的结果,left将得到 right 的值，也就是上一次循环的结果
int aStart = 0, bStart = 0;
for(int i = 0; i <= len / 2; i++){
left = right;
if((aStart < n) && (bStart >= m || A[aStart] < B[bStart])){
right = A[aStart++];
}else{
right = B[bStart++];
}
}
if((len & 1) == 0){//按位做与运算,看其最后一位是0还是1，亦即len是偶数还是奇数
return (left + right) / 2.0 ;
}else{
return right;
}
}
int main(){
int nums;
cin >> nums;
while(nums--){
int n, m;
cin >> n >> m;
int num1[n], num2[m];
for(int i = 0; i < n; i++)
cin >> num1[i];
for(int j = 0; j < m; j++)
cin >> num2[j];
cout << findMedianSortedArray(num1, n, num2, m) << endl;
}
return 0;
}
参考资料：1041 寻找两个正序数组的中位数_金州饿霸吃不饱的博客-CSDN博客
2 题目：
有一实数序列푎_1,푎_2,…,푎_푁，若푖<푗 且 푎_푖>푎_푗，则(푎_푖,푎_푗)构成了一个逆序对，请使用分治方法求整个序列中逆序对个数，并分析算法的时间复杂性。
算法思路：
就是先将数组分为两个部分，然后在将左右两部分在各分为两部分，直到分为每一个小组都是俩个元素，然后在对这两个元素排序(这里是要用那个创建的临时数组的），先将两个元素派完序后放入临时数组中，然后在将临时数组放入要排序的数组，然后就是在将两两排序后的含有两个元素的子数组合并（这里合并的意思也就是在把两个子数组当成两个元素，再进行排序，当然这里可以看出是递归的思想），然后到最后又将很多的子数组有合并成一个大数组，在合并的过程中统计逆序对的个数。
实现代码：
#include
using namespace std;
int reversePairs(int a[], int left, int right, int temp[]);
int mergeAndCount(int a[], int left, int mid, int right, int temp[]);
int reversePairs(int a[], int n){
if(n < 2){//数组元素只有一个或者零个则不存在逆序对
return 0;
}
int *copy = new int[n];
for(int i = 0; i < n; i++){//先拷贝一份原来的数组
copy [i] = a[i];
}
int *temp = new int[n];//辅助数组temp用来归并两个有序数组
return reversePairs(copy, 0, n-1, temp);
}
int reversePairs(int a[], int left, int right, int temp[]){//计算从区间left-right里逆序对的个数并进行排序
if(left == right){//递归终止条件：当数组里只存在一个元素时，一定不存在逆序对
return 0;
}
int mid = left + (right - left) / 2;//不写成(left+right)/2是为了防止整型溢出
int leftPairs = reversePairs(a, left, mid, temp);//左半部分逆序对个数
int rightPairs = reversePairs(a, mid+1, right, temp);//右半部分逆序对个数
if(a[mid] <= a[mid+1]){//左区间和右区间拼接后已经有序，不用再归并
return leftPairs + rightPairs;
}
int crossPairs = mergeAndCount(a, left, mid, right, temp);//把这个左右两个区间合并一下
return leftPairs + rightPairs + crossPairs;
}
int mergeAndCount(int a[], int left, int mid, int right, int temp[]){
//函数执行前提：左区间left-mid里元素是有序的，右区间mid+1-right里元素是有序的
for(int i = left; i <= right; i++){
temp[i] = a[i];
}
int i = left;//指向左区间的第一个元素
int j = mid + 1;//右区间的第一个元素
int count = 0;//统计逆序对个数
for(int k = left; k <= right; k++){
if(i == mid + 1){//左区间或者右区间里的元素必然会有一个先归并完，所以我们只要将剩余的元素复制到a里即可
a[k] = temp[j];
j++;
}else if(j == right + 1){//右区间先归并完了
a[k] = temp[i];
i++;
}else if(temp[i] <= temp[j]){//把较小的那个先归并回a
a[k] = temp[i];
i++;
}else{//每次当右区间有元素归并回a时，就要计算逆序数
a[k] = temp[j];
j++;
count += (mid - i + 1);
}
}
return count;
}
int main(){
int m;
cin >> m;
while(m--){
int n;
cin >> n;
int *a = new int[n];
int *temp = new int[n];
for(int i = 0; i < n; i++)
cin >> a[i];
cout << reversePairs(a, 0, n-1, temp) << endl;
delete []a;
delete []temp;
}
return 0;
}
参考资料：1013 逆序对_金州饿霸吃不饱的博客-CSDN博客
3 题目：
最大子数组问题。一个包含n个整数（有正有负）的数组A，设计一O(nlogn)算法找出和最大的非空连续子数组。对于此问题你还能设计出O(n)的算法吗？
例如：[0, -2, 3, 5, -1, 2]应返回9；
[-9, -2, -3, -5, -3]应返回-2。
实现代码：
#include
using namespace std;
int maxSubArray(int a[], int n){//想要求最大子数组，那么每次开始的第一个数字最好为正数
int max = a[0];
int sum = a[0];//sum首先指向第一个数
for(int i = 1; i < n; i++){//子数组左端点
if(sum > 0){//只要和为正数
sum += a[i];//就让后一个数先加上来再与max比较大小
}else{
sum = a[i];//若sum为负数，则让sum指向当前子序列的最后一个数作为新的起点
}
if(max < sum){
max = sum;
}
}
return max;
}
int main(){
int m;
cin >> m;
while(m--){
int n;
cin >> n;
int a[n+1];
for(int i = 0; i < n; i++)
cin >> a[i];
cout << maxSubArray(a, n) << endl;
}
return 0;
}
参考资料：1014 最大子数组和_金州饿霸吃不饱的博客-CSDN博客
4 题目：
两元素和为X。给定一个由n 个实数构成的集合S 和另一个实数x，判断S 中是否有两个元素的和为x。试设计一个分治算法求解上述问题，并分析算法的时间复杂度。
算法思路：模拟归并排序过程+二分查找。
实现代码：
#include
using namespace std;
const int maxn = 50001;
void Merge(int a[], int start, int mid, int end, int temp[]){
int i = start, j = mid + 1, k = 0;
while(i <= mid && j <= end){
temp[k++] = a[i] <=a[j] ? a[i++] : a[j++];
}
while(i <= mid){
temp[k++] = a[i++];
}
while(j <= end){
temp[k++] = a[j++];
}
int t = 0;
for(i = start; i <= end; i++){
a[i] = temp[t++];
}
}
void mergeSort(int a[], int start, int end, int temp[]){
if(start < end){//数组里至少有两个元素才可以进行归并
int mid = start + (end - start) / 2;
mergeSort(a, start, mid, temp);
mergeSort(a, mid + 1, end, temp);
Merge(a, start, mid, end, temp);
}
}
bool findX(int a[], int len, int x){//先将数组进行归并排序再用二分查找提高查找效率
if(len < 1)
return false;
int i = 0, j = len - 1;
while(i < j){//二分查找
if((a[i] + a[j]) == x){
return true;//结束while循环
}else if((a[i] + a[j]) < x){
i++;
}else{
j--;
}
}
return false;//最后结束while循环没找到k,返回false
}
int main(){
int m;
cin >> m;
while(m--){
int n, x;
cin >> n >> x;
int a[maxn], temp[maxn];
for(int i = 0; i < n; i++){
cin >> a[i];
}
mergeSort(a, 0, n-1, temp);
if(findX(a, n, x)) {
cout << "yes" << endl;
}else{
cout << "no" << endl;
}
}
return 0;
}
参考资料：1016 两元素和_金州饿霸吃不饱的博客-CSDN博客
5 题目：
定义字符串的左旋转 *** 作：把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串 *** 作的复杂度为O(n)，辅助内存为O(1)。
算法思路：
（三次反转算法）假设原数组序列为abcd1234，要求变换成的数组序列为1234abcd，即循环右移了4位。比较之后，不难看出，其中有两段的顺序是不变的：1234和abcd，可把这两段看成两个整体。右移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成：
1. 逆序排列abcd：abcd1234 → dcba1234；
2. 逆序排列1234：dcba1234 → dcba4321；
3. 全部逆序：dcba4321 → 1234abcd。
实现代码：
#include
#include
using namespace std;
void Reverse(char s[], int start, int end){
for(; start < end; start++, end--){
char temp = s[end];
s[end] = s[start];
s[start] = temp;
}
}
void RightShift(char s[], int n, int k){//n为字符串长度，左移k位
k %= n;//以防左移的位数大于字符串的长度
Reverse(s, 0, k-1);
Reverse(s, k, n-1);
Reverse(s, 0, n-1);
}
int main(){
char s[] = "zxcvbn1234";
int k = 3;
RightShift(s, 10, k);
cout << "左移" << k << "位后的字符串s' = " << s;
return 0;
}
运行结果：
参考资料：数组循环移位算法（左旋字符串）【总结】_jiaolongdy的专栏-CSDN博客
6 题目：
给定푛座建筑物 퐵[1, 2, … , 푛]，每个建筑物 퐵[푖]表示为一个矩形，用三元组퐵[푖]=(푎_푖,푏_푖,ℎ_푖)表示，其中푎_푖表示建筑左下顶点，푏_푖表示建筑的右下顶点，ℎ_푖表示建筑的高，请设计一个 푂(푛log푛)的算法求出这푛座建筑物的天际轮廓。例如，左下图所示中8座建筑的表示分别为(1,5,11), (2,7,6), (3,9,13), (12,16,7), (14,25,3), (19,22,18), (23,29,13)和(24,28,4)，其天际轮廓如右下图所示可用9个高度的变化(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13)和(29,0)表示。另举一个例子，假定只有一个建筑物(1, 5, 11)，其天际轮廓输出为2个高度的变化(1, 11), (5, 0)。
微信扫一扫
支付宝扫一扫
评论列表（0条）