经典面试题：有序矩阵的快速查找
【编者案】算法核心不在于框架用得有多熟练，更多在于逻辑和思维方式，很多情况都需要变换间接建模。本文将通过一个经典的面试题来描述思维过程，引导最终问题建模。
接着面试官要开始放大招了。
2.2逐行二分
一维的可以用二分快速查找，那就分解成一维，一行一行的用二分不就行了吗。
bool solve1(vector<vector<int>> &matrix, ofstream &cout, int x) {
int i, j;
i = 0;
j = matrix[0].size() - 1;
bool flag = false;
while (i < matrix[0].size() && j >= 0) {
if (matrix[i][j] > x) {
--j;
} else if (matrix[i][j] < x) {
++i;
} else {
return true;
}
}
return false;
}
按行二分，缩小列
int searchColumn(vector<vector<int>> &matrix, int up, int right, int x) {
int i, j, mid;
i = 0;
j = right;
while (i < j) {
mid = (i + j) / 2;
if (x < matrix[up][mid]) {
j = mid - 1;
} else if (x > matrix[up][mid]) {
i = mid + 1;
} else {
i = j = mid;
}
}
if (matrix[up][i] > x) --i;
return i;
}
int searchRow(vector<vector<int>> &matrix, int up, int right, int x) {
int i, j, mid;
i = up;
j = matrix.size() - 1;
while (i < j) {
mid = (i + j) / 2;
if (x < matrix[mid][right]) {
j = mid - 1;
} else if (x > matrix[mid][right]) {
i = mid + 1;
} else {
i = j = mid;
}
}
if (matrix[i][right] < x) ++i;
return i;
}
bool solve2(vector<vector<int>> &matrix, ofstream &cout, int x) {
int up, right;
up = 0;
right = matrix[0].size() - 1;
while (!(up == matrix.size() || right < 0)) {
right = searchColumn(matrix, up, right, x);
if (right < 0) continue;
up = searchRow(matrix, up, right, x);
if (up == matrix.size())continue;
if (matrix[up][right] == x) {
return true;
}
}
return false;
}
void dataInit() {
ofstream cout("a.in");
int s = 0;
for (int i = 0; i < 5000; ++i) {
for (int j = 0; j < 5000; ++j) {
cout << s + i + j << " ";
}
s += 4999;
cout << endl;
}
}
目标数：10002500
线性执行效率：
row=2000, column=2500
T1=288
二分执行效率
row=2000, column=2500
T2=10
☞C 和 C++ 不安全？Android 支持 Rust 开发操作系统
☞16岁的雅虎问答，因“不再受欢迎”将永久关闭
☞滴滴、小米启动造车，特斯拉的护城河还能守多久？
[广告]赞助链接：
关注数据与安全，洞悉企业级服务市场：https://www.ijiandao.com/
让资讯触达的更精准有趣：https://www.0xu.cn/
关注KnowSafe微信公众号随时掌握互联网精彩
- Bitfinex比特币被盗事件的黑客因特朗普提前获释出狱 曾被查扣36亿美元的比特币
- Kopia 开源的备份工具，主打轻量级、快捷和灵活。
- 谷歌正在为安卓密码管理器提供通行密钥Passkey迁移 支持将密钥导入到新设备
- 传苹果将弃用高通、博通芯片；华为研发投入排全球第四；微软新文本语音模型可在 3 秒内复制任何人的声音 | 极客头条
- Windows、低代码、AI等5大技术主题“出圈”！Microsoft Build 2022大会即将重磅开启
- 员工离职删库被判10个月
- 如果没准备这些面试题，找工作还是缓一缓吧
- 又拍云出席全球云计算大会，入选云鼎奖“云鼎奖”最具潜力企业奖
- CSDN 读书月来了！全场技术书籍低至 3.5 折起
- 招程序员不要信中医的？ | 从编程的角度看中医
- 因女朋友的一个建议，这位程序员创立仅 551 天公司就被 10 亿美元收购了
- 红旗旗舰级智慧全能电动SUV E-HS9搭载Qualcomm C-V2X解决方案，打造旗舰级智能网联驾乘体验
赞助链接
