Найдите пару i, j такую, что |A[i]−A[j]| совпадает с суммой их разностей с любым элементом массива
Для заданного массива A[] с N неотрицательными целыми числами найдите пару индексов i и j , абсолютная разница между которыми равна сумме разностей индексов с любым другим элементом массива, т. е. | А [я] - А [к] | + | А[к]− А[j] | = | A[i] − A[j] |, где k может быть любым индексом.
Примеры:
Input: N = 3, A[] = {2, 7, 5}
Output: 0 1
Explanation:
For k = 0:
|A[0] – A[0]| + |A[0] – A[1]|
= |2 − 2| + |2 – 7| = 0 + 5 = 5
= |A[0] – A[1]|
For k = 1:
|A[0] – A[1]| + |A[1] – A[1]|
= |2 − 7| + |7 – 7| = 5 + 0 = 5
= |A[0] – A[1]|
For k = 2:
|A[0] – A[2]| + |A[2] – A[1]|
= |2 − 5| + |5 – 7| = 3 + 2 = 5
= |A[0] – A[1]|Input: N = 4, arr[] = {5, 9, 1, 3}
Output: 1 2
Explanation:
For k = 0:
|A[1] – A[0]| + |A[0] – A[2]|
= |9 − 5| + |5 – 1| = 4 + 4 = 8
= |A[1] – A[2]|
For k = 1:
|A[1] – A[1]| + |A[1] – A[2]|
= |9 − 9| + |9 – 1| = 0 + 8 = 8
= |A[1] – A[2]|
For k = 2:
|A[1] – A[2]| + |A[2] – A[2]|
= |9 − 1| + |1 – 1| = 8 + 0 = 8
= |A[1] – A[2]|
For k = 3:
|A[1] – A[3]| + |A[3] – A[2]|
= |9 − 3| + |3 – 1| = 6 + 2 = 8
= |A[1] – A[2]|
Подход: Задача может быть решена с помощью следующего математического наблюдения:
Depending on the relation between A[i], A[j] and A[k], the inequality can be written in the following 4 ways:
When A[i] ≥ A[k] ≥ A[j]:
A[i] − A[k] + A[k]− A[j] = A[i] − A[j]
=> A[i] – A[j] = A[i] − A[j]When A[k] ≥ A[i], A[k] ≥ A[j]:
A[k] − A[i] + A[k]− A[j] = |A[i] − A[j]|
=> 2*A[k] – A[i] – A[j] = |A[i] − A[j]|When A[i] ≥ A[k], A[j] ≥ A[k]:
A[i] − A[k] – A[k]+ A[j] = |A[i] − A[j]|
=> A[i] + A[j] – 2*A[k] = |A[i] − A[j]|When A[j] ≥ A[k] ≥ A[i]:
– A[i] + A[k] – A[k] + A[j] = – A[i] + A[j]
=> A[j] – A[i] = A[j] − A[i].From the above equations, it is clear that if value of A[i] and A[j] are not the extreme values of the array then the probability of the equation being satisfied depends on the value of A[k] and will not hold true when A[k] lies outside the range of [A[i], A[j]].
На основании приведенного выше наблюдения ясно, что значение A[i] и A[j] должно быть максимальным и минимальным среди элементов массива. Выполните следующие шаги, чтобы решить проблему:
- Пройдите массив от k = 0 до N-1 :
- Обновите индекс максимального элемента (скажем, i ), если A[k] больше, чем A[i].
- Обновите индекс минимального элемента (скажем, j ), если A[k] меньше, чем A[j].
- Верните пару (i, j) в качестве ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N)
Вспомогательное пространство: O(1)