La solution O(n) correcte est assez compliquée et nécessite une quantité importante de texte, de code et de compétences pour l'expliquer et la prouver. Plus précisément, il faut 3 pages pour le faire de façon convaincante, comme on peut le voir en détail ici http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf (trouvé par simonzack dans les commentaires).
Il s'agit essentiellement d'un algorithme astucieux de division et de conquête qui, entre autres choses, tire parti du fait que, dans une matrice triée n par n, on peut trouver en O(n) la quantité d'éléments qui sont plus petits/grands qu'un nombre donné k . Il décompose récursivement la matrice en sous-matrices plus petites ( en ne prenant que les lignes et colonnes impaires, ce qui donne une sous-matrice qui a n/2 colums et n/2 rangées ) qui, combiné à l'étape ci-dessus, donne une complexité de O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n) . C'est fou !
Je ne peux pas l'expliquer mieux que le journal, c'est pourquoi je vais vous expliquer plus simplement, O(n logn) à la place :) .
Solution O(n * logn) :
C'est une interview ! Tu ne peux pas obtenir ça O(n) solution en temps voulu. Alors, pourquoi ne pas proposer une solution qui, même si elle n'est pas optimale, montre que vous pouvez faire mieux que l'autre solution évidente ? O(n²) candidats ?
Je vais me servir de la O(n) algorithme mentionné ci-dessus, pour trouver le nombre de nombres qui sont plus petits/grands qu'un nombre donné k dans un classement n-by-n matrice. Gardez à l'esprit que nous n'avons pas besoin d'une matrice réelle ! La somme cartésienne de deux tableaux de taille n tel qu'il est décrit par le PO, donne un résultat trié. n-by-n que nous pouvons simuler en considérant les éléments du tableau comme suit :
a[3] = {1, 5, 9};
b[3] = {4, 6, 8};
//a + b:
{1+4, 1+6, 1+8,
5+4, 5+6, 5+8,
9+4, 9+6, 9+8}
Ainsi, chaque ligne contient des nombres non décroissants, de même que chaque colonne. Maintenant, supposons que l'on vous donne un nombre k . Nous voulons trouver dans O(n) combien de nombres dans cette matrice sont plus petits que k et combien sont supérieurs. De toute évidence, si les deux valeurs sont inférieures à (n²+1)/2 c'est-à-dire k est notre médiane !
L'algorithme est assez simple :
int smaller_than_k(int k){
int x = 0, j = n-1;
for(int i = 0; i < n; ++i){
while(j >= 0 && k <= a[i]+b[j]){
--j;
}
x += j+1;
}
return x;
}
Il s'agit essentiellement de compter combien d'éléments répondent à la condition à chaque rangée. Puisque les lignes et les colonnes sont déjà triées comme indiqué ci-dessus, le résultat sera correct. Et comme les deux i et j itérer au maximum n fois chacun, l'algorithme est O(n) [ Notez que j n'est pas réinitialisée dans le cadre de la for boucle ]. Le site greater_than_k L'algorithme est similaire.
Maintenant, comment choisir k ? C'est la logn partie. Recherche binaire ! Comme cela a été mentionné dans d'autres réponses/commentaires, la médiane doit être une valeur contenue dans ce tableau :
candidates[n] = {a[0]+b[n-1], a[1]+b[n-2],... a[n-1]+b[0]}; .
Il suffit de trier ce tableau [également O(n*logn) ], et lancer la recherche binaire sur celui-ci. Puisque le tableau est maintenant dans un ordre non décroissant, il est facile de remarquer que la quantité de nombres plus petits que chaque nombre candidate[i] est également une valeur non décroissante (fonction monotone), ce qui la rend adaptée à la recherche binaire. Le plus grand nombre k = candidate[i] dont le résultat smaller_than_k(k) est plus petit que (n²+1)/2 est la réponse, et s'obtient en log(n) itérations :
int b_search(){
int lo = 0, hi = n, mid, n2 = (n²+1)/2;
while(hi-lo > 1){
mid = (hi+lo)/2;
if(smaller_than_k(candidate[mid]) < n2)
lo = mid;
else
hi = mid;
}
return candidate[lo]; // the median
}
