Calcola coppia adiacente

4

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?

    
posta Chander Shivdasani 14.03.2015 - 00:43
fonte

1 risposta

4

L'array di input che hai è:

0, 3, 3, 7, 5, 3, 11, 1

Immagina che la matrice invece sarebbe questa:

0, 1, 3, 3, 3, 5, 7, 11

Se la matrice fosse organizzata in quel modo, allora potreste scorrere l'array e contare più facilmente le coppie.

0 --> 1
1 --> 3, 3, 3
3 --> 3, 3, 5
3 --> 3, 5
3 --> 5
5 --> 7
7 --> 11

Questo è 1 + 3 + 3 + 2 + 1 + 1 + 1 = 12 coppie. Lo stesso numero che hai trovato prima. Coincidenza? Penso di no.

Ora, se ci fosse un modo per riordinare la matrice per farla sembrare così .... Oh, So !

La complessità del tempo? O (n) per le coppie di cicli e conteggi nell'array ordinato e O (n log n) per l'ordinamento dell'array. Quindi O (n log n + n) = O (n log n)

    
risposta data 14.03.2015 - 01:26
fonte

Leggi altre domande sui tag