从左上角开始BFS吗
是不是很像海岛题。。不对，老老实实从左到右好像也没差。。
可以先对最后一列二分，找到全部小于n的列
剩下的部分从下往上搜
一直找每一行第一个大于n的位置，累加即可。
我觉得这是正解
对哦，谢谢
写下伪代码，欢迎补充
class Element implements Comparable<Element> {
int x;
int y;
long val;
public Element(int x, int y) {
this.x = x;
this.y = y;
this.val = matrix[x][y];
}
@Override
public int compareTo(Element that) {
return Long.compare(this.val, that.val);
}
@Override
public String toString() {
return "[x=" + x + ", y=" + y + "]";
}
}
方法是：
int target;
Queue<Element> q = new PriorityQueue<>();
q.add(new Element(x, y)); // 左上角
while (true) {
Element cur = q.poll();
q.add(new Element(cur.x + 1, cur.y));
q.add(new Element(cur.x, cur.y + 1));
if (cur.val == target) {
return;
}
}
Bruteforce的想法：
- 考虑m和n的大小关系：
m<n : 对每一行做binary-search，找到最后一个<=3的位置，count一下包含该位置之前的元素。
m>=n: 对每一列做binary-search，找到最后一个<=3的位置，count一下包含该位置之前的元素。
T(n) = min(m,n)log(max(m,n))
2.维持一个min-heap，输入每一行/每一列队首元素，pop出最小元素，并且放入该行/列下一个元素。直到pop出元素>3
T(n) = <=3的元素个数*log(min(m, n))
这题有点像 leetcode 378 https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
来自群里：
感觉是先按行二分，扔掉matrix[row][0]>3的部分，然后再二分，扔掉matrix[row][-1]<=3的部分(这部分加到结果里面)，剩下的按列二分
从左下角开始，若matrix[row,col]<=n,col++直到找到>n的 然后row–直到第一行
找到第一行最后等于n的数记住下标加上然后向下移动如果比n大向左移动直到找到等于n依次直到最后一行
感觉像 240. Search a 2D Matrix II https://leetcode.com/problems/search-a-2d-matrix-ii/
我的思路就是从左下角开始做，把每一行小于等于target的个数算出来加到res里。实际代码写出来的时候为了handle corner case，我选择j从 -1开始，每次用matrix[i][j + 1]跟target去比较。
public int count(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
int res = 0;
int row = matrix.length, col = matrix[0].length;
int i = row - 1, j = -1; //从最后一行 第-1列(第0列左边)开始
while(i >= 0 && j < col) {
if (j + 1 < col && matrix[i][j + 1] <= target) j++; //如果当前右边的这个数小于等于target，就右移
else {
res += j + 1; //这一行有j + 1个数小于等于target
i--; //进入上一行
}
}
return res;
}
Swift版本：
func countMatrix(_ matrix: [[Int]], _ target: Int) -> Int {
if matrix.count == 0 {return 0}
let rows = matrix.count
let cols = matrix[0].count
var count = 0
var i = rows-1
var j = 0
// 一行中最左边的数字在行号和列好比它大的所有数字中是最小的，所以可以整行排除。
while i >= 0 && matrix[i][0] > target {
i -= 1
count += cols
}
while i >= 0 && j <= cols - 1 {
let cur = matrix[i][j]
// 如果当前数字大于等于target，那么同行右边的数字都会大于等于target，然后count需要加上这些个数
if cur >= target {
count += (cols - j)
i -= 1
}else{
j += 1
}
}
return count
}