Trouver la médiane de la sum des tableaux

Deux tableaux sortingés de longueur n sont donnés et la question est de trouver, dans O ( n ) time, la médiane de leur tableau de sum, qui contient toutes les sums possibles entre chaque élément du tableau A et chaque élément du tableau B.

Par exemple: Soit A [2,4,6] et B [1,3,5] les deux tableaux donnés. Le tableau de sum est [2+1,2+3,2+5,4+1,4+3,4+5,6+1,6+3,6+5] . Trouvez la médiane de ce tableau dans O ( n ).

Résoudre la question dans O ( n ^ 2 ) est assez simple, mais y a-t-il une solution O ( n ) à ce problème?

Note: Ceci est une question d’interview posée à l’un de mes amis et l’intervieweur était tout à fait sûr qu’il puisse être résolu en O ( n ) temps.

La solution O (n) correcte est assez compliquée et nécessite beaucoup de texte, de code et de compétences pour expliquer et prouver. Plus précisément, il faut 3 pages pour le faire de manière 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).

C’est un algorithme intelligent de division et de conquête qui, entre autres, tire parti du fait que dans une masortingce sortingée par n, on peut trouver dans O(n) la quantité d’éléments plus petits / plus grands qu’un nombre donné k . Il décompose récursivement la masortingce en sous-masortingces plus petites ( en ne prenant que les lignes et les colonnes impaires, ce qui donne une sous-masortingce de n/2 colonnes et n/2 lignes ) qui, combinée à l’étape ci-dessus, entraîne 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 papier, c’est pourquoi je vais vous expliquer une solution plus simple, O(n logn) à la place 🙂 .


Solution O (n * logn):

C’est une interview! Vous ne pouvez pas obtenir cette solution O(n) à temps. Alors, pourquoi ne pas proposer une solution qui, sans être optimale, montre que vous pouvez faire mieux que les autres candidats O(n²) évidents?

Je vais utiliser l’algorithme O(n) mentionné ci-dessus pour trouver la quantité de nombres plus petite / plus grande qu’un nombre donné k dans une masortingce sortingée n-by-n . Gardez à l’esprit que nous n’avons pas besoin d’une masortingce réelle! La sum cartésienne de deux tableaux de taille n , décrite par l’OP, donne une masortingce sortingée 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, ainsi que chaque colonne. Maintenant, prétendez que vous avez reçu un numéro k . Nous voulons trouver dans O(n) combien de nombres dans cette masortingce sont plus petits que k et combien sont plus grands. Clairement, si les deux valeurs sont inférieures à (n²+1)/2 , cela signifie que 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 le nombre d'éléments correspondant à la condition de chaque ligne. Comme les lignes et les colonnes sont déjà sortingées comme indiqué ci-dessus, cela donnera le résultat correct. Et comme i et j iterate au plus n fois chacun, l'algorithme est O(n) [ Notez que j n'est pas réinitialisé dans la boucle for ]. L'algorithme greater_than_k est similaire.

Maintenant, comment choisissons-nous k ? C'est la partie logn . Recherche binary! 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 sortinger ce tableau [également O(n*logn) ], et lancez la recherche binary sur celui-ci. Comme le tableau est maintenant dans un ordre non décroissant, il est facile de noter que la quantité de nombres plus petits que chaque candidate[i] est également une valeur non décroissante (fonction monotone), ce qui le rend approprié pour la recherche binary. . Le plus grand nombre k = candidate[i] dont le résultat smaller_than_k(k) inférieur à (n²+1)/2 est la réponse, et est obtenu en itérations log(n) :

 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 } 

Disons que les tableaux sont A = {A[1] ... A[n]} , et B = {B[1] ... B[n]} , et le tableau de sum par paires est C = {A[i] + B[j], where 1 <= i <= n, 1 <= j <= n} qui a n^2 éléments et il faut trouver sa médiane.

La médiane de C doit être un élément du tableau D = {A[1] + B[n], A[2] + B[n - 1], ... A[n] + B[1]} : si vous fixez A[i] et considérez toutes les sums A[i] + B[j] , vous verriez que le seul A[i] + B[j = n + 1 - i] (qui est l'un des D ) pourrait être la médiane. C'est-à-dire que ce n'est peut-être pas la médiane, mais si ce n'est pas le cas, alors toutes les autres A[i] + B[j] sont pas également médianes.

Ceci peut être prouvé en considérant tous les B[j] et en comptant le nombre de valeurs inférieures et le nombre de valeurs supérieures à A[i] + B[j] (nous pouvons le faire avec précision car les deux tableaux sont sortingés - le calcul est un peu désordonné). Vous verriez que pour A[i] + B[n + 1 - j] ces deux comptes sont les plus "équilibrés".

Le problème se réduit alors à trouver la médiane de D , qui ne comporte que n éléments. Un algorithme tel que celui de Hoare fonctionnera.

MISE À JOUR : cette réponse est fausse. La vraie conclusion est que la médiane est l 'un des éléments de D , mais alors la médiane de D est différente de la médiane de C

Cela ne marche pas ?:

Vous pouvez calculer le rang d’un nombre en temps linéaire tant que A et B sont sortingés. La technique que vous utilisez pour calculer le rang peut également être utilisée pour trouver toutes les choses dans A+B qui se situent entre une limite inférieure et une limite supérieure dans le temps linéaire de la taille de la sortie plus |A|+|B| .

Échantillonner au hasard n choses de A+B Prenez la médiane, dites foo . Calculer le rang de foo . Avec une probabilité constante, le rang de foo situe à n du rang de la médiane. Continuez ainsi (nombre de fois constant attendu) jusqu’à ce que vous ayez des limites inférieures et supérieures sur la médiane qui se situent à 2n unes des autres. (Tout ce processus prend du temps linéaire prévu, mais c’est évidemment lent.)

Il ne vous rest plus qu’à énumérer tout ce qui se trouve entre les limites et à effectuer une sélection linéaire sur une liste de taille linéaire.

(Indépendamment, je n’excuserais pas l’intervieweur d’avoir posé une question aussi évidente.)

EDIT : Vous pouvez calculer le rang d’un nombre x en faisant quelque chose comme ceci:

 Set i = j = 0. While j < |B| and A[i] + B[j] <= x, j++. While i < |A| { While A[i] + B[j] > x and j >= 0, j--. If j < 0, break. rank += j+1. i++. } 

AUTRE ÉDITION : En fait, l'astuce ci-dessus ne fait que restreindre l'espace candidat à environ n log (n) membres de A+B Vous avez alors un problème de sélection général dans un univers de taille n log (n); vous pouvez faire le même tour une fois de plus et trouver une plage de taille proportionnelle à sqrt (n) log (n) où vous faites la sélection.

Voici pourquoi: Si vous échantillonnez k choses à partir d’un ensemble n et prenez la médiane, l’ordre de la médiane de l’échantillon se situe entre le (1/2 - sqrt (log (n) / k)) th et le (1/2 + sqrt (log (n) / k)) les éléments avec une probabilité au moins constante. Lorsque n = | A + B |, nous voudrons prendre k = sqrt (n) et nous obtenons une plage d'environ sqrt (n log n) éléments --- c'est à propos de | A | log | A |. Mais vous le faites à nouveau et vous obtenez une plage de l'ordre de sqrt (n) polylog (n).

Vous devez utiliser un algorithme de sélection pour trouver la médiane d’une liste non sortingée dans O (n). Regardez ceci: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm