Как упоминалось в названии, я хочу найти пары элементов с разницей K
example k=4 and a[]={7 ,6 23,19,10,11,9,3,15}
output should be :
7,11
7,3
6,10
19,23
15,19
15,11
Я прочитал предыдущие сообщения в SO "найти пару чисел в массиве, которые добавляют к заданной сумме"
Чтобы найти эффективное решение, сколько времени требуется? Является ли временная сложность O(nlogn) или O(n)?
Я попытался сделать это с помощью техники разделения и покорения, но я не понимаю подсказки о состоянии выхода...
Если эффективное решение включает сортировку входного массива и управление элементами с помощью двух указателей, то я думаю, что я должен взять минимум O(nlogn)...
Существует ли какая-либо математическая техника, которая приносит решение в O(n). Любая помощь приветствуется.
Вы можете сделать это в O (n) с хеш-таблицей. Поместите все числа в хэш для O (n), а затем снова просмотрите их, ища number[i]+k. Хэш-таблица возвращает "Да" или "Нет" в O (1), и вам нужно пройти все числа, поэтому общее число равно O (n). Любая структура набора с установкой O (1) и временем проверки O (1) будет работать вместо хеш-таблицы.
Простым решением в O (n * Log (n)) является сортировка вашего массива, а затем переход через ваш массив с помощью этой функции:
void find_pairs(int n, int array[], int k)
{
int first = 0;
int second = 0;
while (second < n)
{
while (array[second] < array[first]+k)
second++;
if (array[second] == array[first]+k)
printf("%d, %d\n", array[first], array[second]);
first++;
}
}
Это решение не использует дополнительное пространство, в отличие от решения с хэш-таблицей.
Можно сделать одну вещь, используя индексирование в O (n)
arr, индексированный в списке ввода.i находится во входном списке, затем установите arr[i] = truearr от младшего целого до наивысшего целого числа следующим образом:
true в i -м индексе, запишите этот индекс.arr[i+k]. Если да, то i и i+k номера являются необходимой паройi+1