經(jīng)典面試題：有序矩陣的快速查找
算法核心不在于框架用得有多熟練，更多在于邏輯和思維方式，很多情況都需要變換間接建模。本文將通過一個(gè)經(jīng)典的面試題來描述思維過程，引導(dǎo)最終問題建模。
最近招聘市場(chǎng)各路神仙出沒，小K也打算去湊一下熱鬧。
熱身運(yùn)動(dòng)，小K先和面試官過了幾招，不分勝負(fù)。
接著面試官要開始放大招了。
這招怎么化解呢，等小K先思考2分鐘。
一般是先想一下有沒有可以套用的算法框架，如果不能發(fā)現(xiàn)很明顯的算法，可以先分析問題的規(guī)律，然后再嘗試變換間接建模。我們先嘗試把所有能發(fā)現(xiàn)的規(guī)律都找出來。
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;
}
}
目標(biāo)數(shù)：10002500
線性執(zhí)行效率：
row=2000, column=2500
T1=288
二分執(zhí)行效率
row=2000, column=2500
T2=10
評(píng)論
圖片
表情