Mi è stato dato il seguente problema:
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty zero-indexed array A consisting of N integers is given.
A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value
in the array lies strictly between values A[P] and A[Q].
For example, in array A such that:
A[0] = 0 A[1] = 3 A[2] = 3
A[3] = 7 A[4] = 5 A[5] = 3
A[6] = 11 A[7] = 1
the following pairs of indices have adjacent values:
(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7).
For example, indices 4 and 5 have adjacent values because there is no value in array A that lies
strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4,
and it is not present in the array.
Write a function that returns number of adjacent values
La mia soluzione era la seguente:
- Per ogni coppia, controlla se ci sono altri elementi che si trovano in questo intervallo
- In caso contrario, incrementa il conteggio di Pair adiacenti
- Altrimenti, procedi con un'altra coppia.
Questo approccio richiede O (N ^ 3). Volevo sapere se esiste un modo migliore per risolvere questo problema?