#3842. 兔猫信奥学院的“星辰矩阵”探秘
兔猫信奥学院的“星辰矩阵”探秘
🏫 题目名称:兔猫信奥学院的“星辰矩阵”探秘
🐰🐱 题目描述
在兔猫信奥学院的天文观测塔顶,加菲老师布置了一块神秘的“星辰矩阵”——一个 \(m\times n\) 的整数阵列,记录了走廊两端星座的编号。小兔和小猫要在这块矩阵里寻找一颗特定星辰的编号。
这块矩阵满足两条神奇的法则:
- 每行从左到右是非严格递增的(允许相邻相等)。
- 每行首元素都大于上一行的尾元素。
加菲老师对他们说:
“给定这块矩阵
matrix
和一个目标编号target
,如果它存在于矩阵中,返回true
;否则返回false
。你需要在 \(O(\log(mn))\) 的时间内完成搜寻!”
📥 输入格式
第一行:三个整数 m, n, target
接下来 m 行:每行 n 个整数,表示矩阵 matrix[i][0..n-1]
- \(1 \le m, n \le 100\)
- \(-10^4 \le matrix[i][j],\;target \le 10^4\)
matrix
满足 每行非降 且 行首大于前一行行尾
📤 输出格式
如果 target 存在于矩阵中,输出 true;否则输出 false。
💡 输入输出样例
3 4 3
1 3 5 7
10 11 16 20
23 30 34 60
true
3 4 13
1 3 5 7
10 11 16 20
23 30 34 60
false
📊 数据范围
- 矩阵行数 \(m\)、列数 \(n\) 最多 100
- 元素及目标编号在区间 \([-10^4,10^4]\)
- 要求算法时间复杂度接近 \(O(\log(mn))\)