算法基础课题解合集
二分
二分思路
既然要找两个和为 x 的数,那么我们可以把它转换成确定了一个 y 为 Ai 然后快速在 B 中找出 x−y 的问题。
显然我们可以二分查找,算法复杂度为 O(nlogn),可以AC。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N], b[N];
int n, m, x;
int main() {
cin >> n >> m >> x;
for (int i = 0; i < n; i ++) cin >> a[i];
for (int i = 0; i < m; i ++) cin >> b[i];
for (int i = 0; i < n; i ++) {
int y = x - a[i];
int l = 0, r = m - 1;
while (l <= r) {
int mid = l + r >> 1;
if (b[mid] == y) {
cout << i << " " << mid << endl;
return 0;
} else if (b[mid] < y) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return 0;
}
双指针
双指针思路
我们先简化一下问题,变成求 Ai+Bj>=x 且 j 要最小。
我们用可以一个指针 i 枚举 A 中的所有数,而 j 则用来枚举 B,但由于数组是单调递增的,所以如果 Ai+Bj≥x 那么 Bj+1 到 Bm 就不可能是答案。
所以 j 是只能递减的,如此,我们便可以用 O(n+m) 的时间复杂度通过这道题。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
int main() {
cin >> n >> m >> x;
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= m; i ++) cin >> b[i];
for (int i = 1, j = m; i <= n; i ++) {
while (j >= 0 && a[i] + b[j] >= x) j --;
if (j >= 0 && b[j + 1] + a[i] == x) // 注意这里的下标,感谢大佬的指正
cout << i - 1 << " " << j << endl;
}
return 0;
}
哈希
思路
我们可以在输入 A 时把每个数存进哈希表里,对于每个输入的 Bi 看看 x−Bi 是否出现与哈希表即可。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 100010;
int n, m, x;
int a[N], b[N];
unordered_map<int, int> h;
int main() {
cin >> n >> m >> x;
for (int i = 0; i < n; i ++) {
cin >> a[i];
h[a[i]] = i;
}
for (int i = 0; i < m; i ++) {
cin >> b[i];
if (h.count(x - b[i]))
cout << h[x - b[i]] << " " << i << endl;
}
return 0;
}
好啦,这篇题解到这里就结束啦!感谢观看!!!
writerbyacwing : 天元之弈
大佬,第一个二分写法
if (b[mid] == y) { cout << i << " " << mid << endl; return 0;
如果不return 0为什么会超时,怎么想到+return 0的
因为这题有唯一解
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 100010; int n, m, x; int a[N], b[N]; int main() { cin >> n >> m >> x; for (int i = 0; i < n; i ++) cin >> a[i]; for (int i = 0; i < m; i ++) cin >> b[i]; for (int i = 0, j = m - 1; i < n; i ++) { while (j >= 0 && a[i] + b[j] >= x) j --; if (j >= 0 && b[j + 1] + a[i] == x) //这里必须是if (j >= -1 && b[j + 1] + a[i] == x) cout << i << " " << j + 1 << endl; } return 0; }
例子:
2 3 5
1 3
2 2
可以知道3 + 2 = 5,3的位置是i = 1,5的位置是j = 0,而对应我们的程序运行对应的解为i = 1;j = -1
而我们的程序if (j >= 0 && b[j + 1] + a[i] == x)会把这种情况退出,从而导致无解,所以要改为if (j >= -1 && b[j + 1] + a[i] == x)
双指针算法
这数据是不是有问题,B的长度是2不是3
这是y总的测试数据,没有问题,
m = 3,说明B数组的长度就是3,但你B只有两个数,显然有问题啊
那里打错了,是二
你可以试试
2 2 3
1 2
1 3
已经修改了,强迫症不太喜欢-1,就把数组下标改了qwq
#include <iostream> using namespace std; const int N=10e5+10; int n,m,x,a[N],b[N]; int main() { cin>>n>>m>>x; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int j=0;j<m;j++) scanf("%d",&b[j]); //我们先简化一下问题,变成求 Ai+Bj>=x且j要最小 for(int i=0,j=m-1;i<n;i++){ while( j>=0 && a[i]+b[j]>x ) j--; if( a[i]+b[j]==x ){ cout<<i<<" "<<j<<endl; break; } } return 0; }
这样也可以,就是楼主的思路,稍微简洁一些
大佬啊哈希表真的妙
天才啊,老弟,双指针解法犀利;
感觉查找匹配还是哈希比较好写
#include [HTML_REMOVED]
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int main(){
int n1,n2,x;
cin >> n1 >> n2 >> x;
for(int i=0; i<n1; i++) cin >> a[i]; for(int j=0; j<n2; j++) cin >> b[j]; int j = n2 - 1; for(int i =0; i<n1; i++) { while(j>0 && a[i] + b[j] > x) j--; if(a[i] + b[j] == x) cout << i << " " << j << endl; } return 0;
}
双指针不需要去特判J,不让他等于0就好了
双指针有点不太懂为什么等于也要j–
我咋就想不到呢
这个哈希,实在是太秀了
牛逼啊
#include [HTML_REMOVED]
#include [HTML_REMOVED]
int a[100010],b[100010];
int n,m,x;
int main()
{
scanf(“%d%d%d”,&n,&m,&x);
for(int i=0;i<n;i)
scanf(“%d”,&a[i]);
int i=0;
int j=m;
for(i=0;i<m;i)
scanf(“%d”,&b[i]);
for(i=0;i<n;i++)
{
j=x-a[i];
int l=0;
int r=m-1;
while(l<=r)//大佬为什么这里的=去掉后就得不出正确结果了? 有点想不明白,大佬能解释一下吗
{int mid=l+r >>1; if(b[mid]==j) { printf("%d %d",i,mid); return 0; } else if(b[mid]>j) r=mid-1; else l=mid+1;}
}
return 0;
}
这道题用二分的话,每个a[i]都会在b[i]进行二分查找, 最坏的时间复杂度不应该是n✖二分的复杂度nlogn吗,这样子不会超时吗
二分的复杂度是 O(logn) 哦
但是你要循环n次,每次都要二分查找,时间复杂度最坏不就变成n^2*nlogn了
对呀,所以是 O(n×logn) 啊
我一次二分是 nlogn 那么做 n 次二分,就是 nlogn,可以看代码,for 一共 n 次,内部循环二分每次 logn
哦哦,我的错,你是对的OAO
二分写法里的l = mid + 1 我能理解,但为什么r = mid - 1,而不是r = mid啊,我r = mid会超时是什么原因呢
注意看我写的是 l<=r,这样子的模板虽然时间不如y总的(会多执行一次),但是固定一个模板,不容易错
哇,好牛,学到了个新方法,想问一下如果我想用y总的板子为什么会错呀,这个样例无输出
1 2 6
1
3 5
标准答案
0 1
你代码发我看看呗
#include<iostream> #include<cstdio> #include<set> using namespace std; const int N=100010; int a[N],b[N]; int main() { int n,m,x; cin>>n>>m>>x; for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<m;i++) scanf("%d",&b[i]); for(int i=0;i<n;i++) { int l=0,r=m-1; while(l<r) { int mid=l+r>>1; if(b[mid]>=(x-a[i])) r=mid; else l=mid+1; } if(b[l]+a[i]==x) { cout<<l<<" "<<i<<endl; break; } } return 0; }
这样是WA的为什么呢
输出反了,先输出
i
再是l
,注意你上面写的是b[l]
和a[i]
。哈希的时间复杂度是多少呢
O(1)
大概应该是O(N)吧
好呢
哈希一步是O(1),循环n次就是O(n)