Нахождение ближайших чисел в двух массивах
Я должен найти ближайшие числа в двух массивах и показывает их разницу. Я использую цикл для этого, но это занимает слишком много времени. Вы знаете какой-нибудь способ сделать этот алгоритм быстрее?
#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
Другие решения
Если вы сортируете их, вы можете оптимизировать алгоритм, чтобы он работал намного быстрее. Когда оба ваших массива отсортированы, вы можете проверить один за другим и сравнить их меньше, чем ваш текущий алгоритм. Потому что вы пропустите некоторые из них, так как вы знаете, что они отсортированы.
Кстати, так как вы получаете номера от пользователя, я предлагаю вам поместить номера в отсортированном виде. Каждый раз, когда пользователь вводит число, помещайте число в место, где числа после него больше его, а числа до него меньше его. Чтобы сделать такую вещь, возможно, лучше использовать связанный список (или проще).
detector