la solution O(n) correcte est assez compliquée, et nécessite une quantité importante de texte, de code et d'habileté pour expliquer et prouver. Plus précisément, il faut 3 pages pour le faire de façon convaincante, comme on peut le voir dans les détails 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 diviser pour régner qui, entre autres choses, tire avantage du fait que dans une matrice n-par-n triée, on peut trouver O(n) le montant des éléments de plus petite taille/plus qu'un nombre donné k. Il décompose récursivement la matrice en sous-groupes plus petits (en prenant seulement les lignes et les colonnes impaires, résultant en une sous-matrice qui a n/2 colonnes et n/2 lignes) qui, combiné avec l'étape ci-dessus, résulte en une complexité de O(n) + O(n/2) + O(n/4)... = O(2*n) = O(n). Il est fou!

je ne peux pas expliquer mieux que le papier, c'est pourquoi je vais vous expliquer plus simple, O(n logn) solution à la place :).

O (N * logn) solution:

C'est une interview! Vous ne pouvez pas obtenir que l' O(n) solution à temps. Alors, pourquoi ne pas fournir une solution qui, bien que non optimale, montre que vous pouvez faire mieux que l'autre évidente O(n²) les candidats?

je vais faire usage de l' O(n) algorithme mentionné ci-dessus, pour trouver la quantité de nombres qui sont plus petits / plus grands qu'un nombre donné k triés n-by-n de la matrice. Gardez à l'esprit que nous n'avons pas besoin d'une réelle matrice! La somme cartésienne de deux tableaux de taille n, comme décrit par L'OP, résulte en unn-by-n matrix, 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, ainsi que chaque colonne. Maintenant, faites comme si vous aviez un numéro!--5-->. Nous voulons trouver dans O(n) combien de numéros dans cette matrice sont plus petit que k, et combien sont grand. Clairement, si les deux valeurs sont inférieures à (n²+1)/2 qui signifie 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;
}

cela compte essentiellement combien d'éléments correspondent à la condition à chaque rangée. Puisque les lignes et les colonnes sont déjà triées comme vu ci-dessus, cela fournira le résultat correct. Et comme les deux i et j itérer à la plupart des n chaque fois, l'algorithme est O(n) [Notez que j n'est pas réinitialisé à l'intérieur for boucle]. greater_than_k algorithme similaire.

maintenant, comment choisir