tratando de resolver Kth Smallest Element in a Sorted Matrix , básicamente encontró una solución con una complejidad de memoria mejor que O (n2).
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 Output: 13 Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13¿Qué está haciendo esta línea de código, por favor, ayúdame a averiguarlo?
mid = (lo + (hi - lo) / 2) >> 0;Aquí está el código completo
var kthSmallest = function(matrix, k) { var n = matrix.length, lo = matrix[0][0] var hi = matrix[n-1][n-1]; var mid, count; while(lo < hi) { mid = (lo + (hi - lo) / 2) >> 0; count = countLEQ(matrix, mid); if (count < k) { lo = mid + 1; } else { hi = mid; } } return lo; }; var countLEQ = function (matrix, x) { var n = matrix.length; var count = 0; var j; matrix.forEach(function(row){ for(j = 0; j < n && row[j] <= x; j++){ ;} count += j }); return count; }; ¿Tengo razón al decir la complejidad del tiempo como O(log n) como su binary search algorithm ?
Tu ayuda es apreciada
Carolina
La complejidad del tiempo está entre O(log n) y O(n), ya que mientras que el bucle externo es de hecho una búsqueda binaria (O(log n)), el método countLEQ es serial (O(n)).
Esta línea:
mid = (lo + (hi - lo) / 2) >> 0 Simplemente calcula un nuevo punto medio, truncando cualquier fracción. Shift right >> 0 hace esto al convertir a int. Esto generalmente se hace usando el operador de doble tilde ( ~~ ): es decir, mid = ~~(lo + (hi - lo) / 2)
mid = (lo + (hi - lo) / 2) >> 0Esto se utiliza para calcular el índice medio en una búsqueda binaria. Está evitando cualquier valor de fracción.
Método alternativo para calcular el índice medio en una búsqueda binaria:
Math.floor((lo + hi) / 2)