Cercando una matrice 2D al momento sublineare

Question

Questo è un problema da una recente intervista di codifica

Scrivere un algoritmo efficiente che cerca un valore in una matrice di n m x.

Questa matrice ha le seguenti proprietà:

1. integer in ciascuna fila sono ordinati crescente da sinistra verso destra.

2. I numeri interi in ogni colonna sono ordinati in ordine crescente dall'alto verso il basso.
   .

   [1, 4, 7, 11, 15] 
   
       [2, 5, 8, 12, 19] 
   
       [3, 6, 9, 16, 22] 
   
       [10, 13, 14, 17, 24] 
   
       [18, 21, 23, 26, 30] 
   

C'è un modo per fare questo sotto O (mn). Non riesco a vedere come si possa fare una ricerca binaria su questo array, poiché non c'è modo di eliminare nulla.

Answer 1

È possibile utilizzare questo semplice algoritmo che sfrutta il fatto che in una matrice con queste proprietà, un valore mtx[i][j] è sempre più piccolo di qualsiasi valore mtx[x][y], dove x > i o y > j, in altre parole, qualsiasi valore a destra e giù:

public static boolean find(int[][] mtx, int val) { 
    int maxCol = mtx[0].length, minCol = 0; 

    for(int i = 0 ; i < mtx.length ; i++) { 
     for(int j = minCol ; j < maxCol ; j++) { 
      if(val == mtx[i][j]) return true; 

      if(val < mtx[i][j]) { 
       maxCol = j; 
       break; 
      } 
     } 

     if(maxCol == 0) break; 

     minCol = 0; 
     if(i != mtx.length-1 && val > mtx[i+1][maxCol-1]) minCol = maxCol-1; 
    } 

    return false; 
} 

L'idea è quella di cercare riga per riga, e se si trova un valore che è più grande, si può smettere di guardare in questa riga e si sa che non c'è bisogno di cercare al di là di quella colonna in righe future. E se il primo valore di una riga è più grande del valore, allora puoi smettere di cercare e restituire false. Inoltre, alla fine di ogni ricerca di riga, controlli la cella dalla riga successiva a maxCol-1, se il valore è maggiore, quindi nel ciclo successivo, puoi saltare tutte le celle precedenti.

Lo scenario peggiore è il valore più grande (o più grande) e la complessità è O (m + n), perché verificherebbe tutta la prima riga, quindi salterà le successive m righe.

Answer 2

Per un dato valore x, esiste un limite che gira attraverso la matrice, più o meno da sinistra inferiore a destra superiore, sempre procedendo verso destra o verso l'alto e separando valori superiori a x da valori inferiori o uguali a X.

Iniziare da sinistra in alto e cercare in basso e a destra in una linea diagonale dritta fino a trovare questo limite frastagliato. (Se si raggiunge per primo un bordo della matrice, basta seguire quel bordo a destra o in basso, continuando la ricerca.) Quindi si passa lungo il confine in entrambe le direzioni finché non viene trovata x o non ci sono più celle di matrice da cercare.

Questa ricerca può attraversare tre sezioni di percorso, ognuna delle quali va solo a destra e in basso, a destra e in alto oa sinistra e in basso. Le lunghezze di tali percorsi sono O (m + n). Quindi l'intera ricerca è O (m + n).