我必须在两个数组中找到最接近的数字并显示它们的差异。我为此使用了一个循环,但是这花费了太多时间。您知道有什么方法可以使该算法更快吗?
#include <cmath>
#include <cstdio>
using namespace std;
long long int red, yellow, minimum = 1000000000, difference = 0;
long long int TC[100001], ZT[100001];
int main()
{
scanf("%d", &red);
for (int y = 0; y < red; ++y)
{
scanf("%d", &TC[y]);
}
scanf("%d", &yellow);
for (int yy = 0; yy < yellow; ++yy)
{
scanf("%d", &ZT[yy]);
}
for (int yyy = 0; yyy < red; ++yyy)
{
for (int i = 0; i < yellow; ++i)
{
difference = abs(TC[yyy] - ZT[i]);
if (difference == 0)
{
minimum = 0;
break;
}
else if (difference < minimum)
minimum = difference;
}
}
printf("%d \n", minimum);
}
应为O(nlgn):
sort two lists
let i = 0, j = 0, minval = abs(list1[0] - list2[0])
as long as both lists have more items:
minval = min(minval, abs(list1[i] - list2[j])
if abs(list1[i + 1] - list2[j]) < abs(list1[i] - list2[j + 1])
increment i
else increment j
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句