題目
在一個二維數(shù)組中稼稿，每一行都按照從左到右遞增的順序排序苔咪，每一列都按照從上到下遞增的順序排序漓概。請完成一共函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)阔墩，判斷數(shù)組中是否含有該整數(shù)
例如下面的二維數(shù)組就是每行嘿架、每列都遞增排序。如果在這個數(shù)組中查找數(shù)字7啸箫，則返回true耸彪，如果查找數(shù)字5，由于數(shù)組不含有該數(shù)字忘苛，則返回false
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
分析
首先我們選取數(shù)組右上角的數(shù)字9蝉娜，由于9大于7，并且9還是第4列的第一個（也是最小的）數(shù)字扎唾，因此7不可能出現(xiàn)在數(shù)字9所在的列召川。于是我們把這一列從需要考慮的區(qū)域內剔除，之后需要分析剩下的3列胸遇。
在所剩下的矩陣中荧呐，位于右上角的數(shù)字是8，同樣8大于7纸镊，因此8所在的列我們也可以剔除倍阐。接下來我們只要分析剩下的2列即可。
在剩下的2列中逗威，數(shù)字2位于數(shù)組的右上角峰搪，2小于7，那么要查找的7可能在2的右邊也可能在下邊凯旭，在前面的步驟中概耻，我們已經將2右邊的列都已經被剔除了使套，也就是說2只能是出現(xiàn)在2的下邊，于是我們把2所在的行剔除鞠柄。在剩下的數(shù)字中侦高，數(shù)字4位于又上角，由于4小于7春锋，同樣剔除4所在的行矫膨。
在剩下的2行中，位于右上角的數(shù)字7正好是我們要查找的期奔，于是查找過程結束。
總結上面查找的過程
我們可以發(fā)現(xiàn)規(guī)律危尿，首先選取數(shù)組中右上角的數(shù)字呐萌，如果該數(shù)字等于要查找的數(shù)字，則查找結束谊娇；如果該數(shù)字大于要查找的數(shù)字肺孤，則剔除這個數(shù)字所在的列；如果該數(shù)字小于要查找的數(shù)字济欢，則剔除數(shù)字所在的行赠堵。
也就是說，如果要查找的數(shù)字不在數(shù)組的右上角法褥，則每一次都在數(shù)組的查找范圍剔除一行或者一列茫叭，這樣每一步都可以縮小查找的范圍，直到找到要查找的數(shù)字半等，或者查找范圍為空
算法從右上角元素開始比較
如果相等就返回揍愁；如果大于則列減少，否則行增加
bool Find(int* matrix, int rows, int columns, int number)
{
bool found = false;
if(matrix != nullptr && rows > 0 && columns > 0)
{
int row = 0;
int column = columns - 1;
while(row < rows && column >=0)
{
if(matrix[row * columns + column] == number) // 使用指針獲取二維數(shù)組的值進行比較
{
found = true;
break;
}
else if(matrix[row * columns + column] > number)
-- column;
else
++ row;
}
}
return found;
}
二維數(shù)組在內存中占據連續(xù)的空間杀饵，在內存中從上到下存儲各行元素莽囤，在同行中按照從左到右的順序存儲，因此我們可以根據行號和列號計算出相當于數(shù)組首地址的偏移量
使用二維數(shù)組
bool find(int target, vector<vector<int>> array)
{
int rows = array.size(); // 矩陣行
int cols = array[0].size(); // 矩陣列數(shù)
bool found = false;
if (rows > 0 && cols > 0)
{
int row = 0; // 第一行
int col = cols - 1; // 最后一列
while (row < rows && col >= 0) {
if (array[row][col] == target) // 當前值跟目標值相等正好找到
{
found = true;
break;
}
else if (array[row][col] > target) // 當前值比目標值大
--col;
else
++row;
}
}
return found;
}
算法從左下角開始比較
相等就返回切距；若大于則列增加朽缎，否則行減少
bool find1(int target, vector<vector<int>> array)
{
int rows = array.size();
int cols = array[0].size();
bool found = false;
if (rows > 0 && cols > 0)
{
int row = rows - 1; // 最后一行
int col = 0; // 第一列
while (row >= 0 && col < cols)
{
if (array[row][col] == target)
{
found = true;
break;
}
else if (array[row][col] > target)
--row;
else
++col;
}
}
return found;
}
暴力解法，兩層for循環(huán)
bool Find(vector<vector<int> > array,int target)
{
int row = 0, col = 0, t = 0;
bool isFound = false;
for(int i = 0; i < array.size( ) ; ++i)
{
for(int j = 0; j < array[i].size( ); ++j)
{
//邊輸入邊驗證
if(false == isFound && target == array[i][j])
{
//已經找到后就沒必要再找了
isFound = true;
}
}
}
return isFound;
}
參考
《劍指offer》
