Javascript 排序矩阵中第 K 小元素的方式

Question

尝试解决 Kth Smallest Element in a Sorted Matrix，基本上您找到了内存复杂度优于 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

这行代码是干什么的请帮我看看？？？

 mid = (lo + (hi - lo) / 2) >> 0;

这是完整的代码

            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;
            };

我说的时间复杂度 O(log n) 和 binary search algorithm 一样正确吗？？？

感谢您的帮助

卡罗琳

Answer 1

时间复杂度介于 O(log n) 和 O(n) 之间，因为虽然外循环确实是二分查找 (O(log n))，但 countLEQ 方法是串行的 (O( n)).

这一行：

mid = (lo + (hi - lo) / 2) >> 0

只是计算一个新的中点，截断任何分数。右移 >> 0 通过转换为 int 来实现。这通常使用双波浪号运算符 (~~) 完成：即 mid = ~~(lo + (hi - lo) / 2)

Answer 2

mid = (lo + (hi - lo) / 2) >> 0

这用于计算二进制搜索中的中间索引。它正在避免任何分数值。

在二进制搜索中计算中间索引的替代方法：

Math.floor((lo + hi) / 2)

Javascript 排序矩阵中第 K 小元素的方式

Javascript way of Kth Smallest Element in a Sorted Matrix

javascript

data-structures

ecmascript-6