內容介紹
本系列我將帶著大家一起刷劍指offer的題目，歡迎大家一起交流一起討論??????，希望能得到大家的👍和🐾🐾
題目介紹：
在一個二維陣列中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣一個二維陣列和一個整數，判斷該陣列中是否含有該整數，
思路：當任取陣列中的一個數字的時候有三種情況：
- 當陣列中選擇的數字剛好等于要尋找的數，則結束尋找
- 如果選擇的數字小于要查找的數，則要查找的數在該數的右邊或下面
- 如果選擇的數字大于要查找的數，則要查找的數在該數的左邊或上面
這樣看起來問題還是很復雜的，但是我們會發現如果從陣列的角度開始尋找那么就只會向一個方向移動，
我們來舉個栗子：比如要在上面的陣列例子中尋找7，我們從右上角開始尋找，右上角元素是9，比7大，所以我們尋找的范圍就縮小到了前三列（第四列剩下的數必然比7大），然后我們再從縮小的陣列的右上角進行尋找，發現是8，所以查找范圍變成前兩列，這時右上角元素為2，比7小，這時我們把范圍縮小為一個3*2的矩陣，此時右上角元素為4，仍然比7小，范圍再次縮小為一個2*2的矩陣，右上角元素為7，成功找到我們需要找的數字，查找結束，
注意：這里我們只能從右上角和左下角進行查找，因為這兩個數剛好一個方向比它小一個方向比它大，這樣才能方便我們縮小范圍，如果是左上角，下面和右邊都比它大這樣就不好縮小范圍了，右下角同理
從分析中我們可以發現一個規律，從右上角開始查找數字，
若比目標數字大則范圍陣列列減一（此時將之前右上角元素列下標減一即可），若比目標數字小則范圍陣列行加一（此時將之前右上角元素行下標加一即可），直達最終找到我們的目標數字，若最終沒找到則說明該數不在陣列中，
代碼實作：
int Find_num(int* pa, int rows, int cols, int num)
{
int flag = 0;//標志位，用來判斷是否找到數字，
int row = 0;
int col = cols - 1;
if (pa != NULL && rows > 0 && cols > 0)//保證輸入都是有效的引數
{
while (row < rows && col >= 0)//若不滿足條件說明查到到陣列范圍外了，說明要找的數不在陣列里面，
{
if (pa[row * cols + col] == num)//二維陣列在記憶體中連續存放，所以可以用首元素地址進行偏移找到二維陣列中任意一個元素，
{
flag = 1;
break;
}
else if (pa[row * cols + col] > num)
{
col--;
}
else
{
row++;
}
}
}
return flag;
}
int main()
{
int i = 0;
int j = 0;
int arr[4][4] = { {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15} };
int n = 0;
int* parr = arr[0];
printf("請輸入你要找的數：");
scanf("%d", &n);
int ret = Find_num(parr, 4, 4, n);
if (ret)
{
printf("找到了\n");
}
else
{
printf("沒有該數字\n");
}
return 0;
}
結果：
作者水平有限，若文章有任何問題歡迎私聊或留言，希望和大家一起學習進步！！！
創作不易，再次希望大家👍支持下，謝謝大家🙏
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/299001.html
標籤：其他