Javascript 排序矩阵中第 K 小元素的方式
Javascript way of Kth Smallest Element in a Sorted Matrix
尝试解决 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
一样正确吗???
感谢您的帮助
卡罗琳
时间复杂度介于 O(log n) 和 O(n) 之间,因为虽然外循环确实是二分查找 (O(log n)),但 countLEQ
方法是串行的 (O( n)).
这一行:
mid = (lo + (hi - lo) / 2) >> 0
只是计算一个新的中点,截断任何分数。右移 >> 0
通过转换为 int 来实现。这通常使用双波浪号运算符 (~~
) 完成:即 mid = ~~(lo + (hi - lo) / 2)
mid = (lo + (hi - lo) / 2) >> 0
这用于计算二进制搜索中的中间索引。它正在避免任何分数值。
在二进制搜索中计算中间索引的替代方法:
Math.floor((lo + hi) / 2)
尝试解决 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
一样正确吗???
感谢您的帮助
卡罗琳
时间复杂度介于 O(log n) 和 O(n) 之间,因为虽然外循环确实是二分查找 (O(log n)),但 countLEQ
方法是串行的 (O( n)).
这一行:
mid = (lo + (hi - lo) / 2) >> 0
只是计算一个新的中点,截断任何分数。右移 >> 0
通过转换为 int 来实现。这通常使用双波浪号运算符 (~~
) 完成:即 mid = ~~(lo + (hi - lo) / 2)
mid = (lo + (hi - lo) / 2) >> 0
这用于计算二进制搜索中的中间索引。它正在避免任何分数值。
在二进制搜索中计算中间索引的替代方法:
Math.floor((lo + hi) / 2)