您好,登錄后才能下訂單哦!
讓人瑟瑟發(fā)抖的面試題
。
。
。
來我們看一下題目
在一個二維數(shù)組中,每一行都按照從左到右遞增的順序操作。每一列都按照從上到下遞增的順序排序。完成代碼,輸入這樣一個二維數(shù)組和一個整數(shù),判斷數(shù)組是否含有該整數(shù)
怎么解決勒???
分析:如果二維數(shù)組是這樣,為了解決問題完全可以把數(shù)組遍歷一遍,但是為了效率,我們需要把時間復雜度降低,為了遍歷最少的數(shù)字,我們需要把行和列分開。所以,我們會從數(shù)組中找一個數(shù)字進行判斷,然而,隨便找一個數(shù)字,只會讓問題變的跟復雜,比如,找一個10,左邊和上邊都比10小,而下邊和右邊都比10大,所以,我們只能找一些特殊點,比如,右上邊,左下邊,只會有一條路讓你選擇。a[row][col],我們拿9舉例,若所找數(shù)字比9大,只需row++;若所找數(shù)字比9小,只需col--;直到最后找到所需數(shù)字。
來看看代碼
#include<iostream>
using namespace std;
bool find(int *arr, int row, int col, int n)
{
bool flag = false;//標記
if (arr != nullptr&&row > 0 && col > 0)//判斷數(shù)組是否存在
{
int _row = 0;
int _col = col - 1;
while (_col>0&&_row<row)
{
if (arr[_row*col + _col] > n)
{
_col--;
}
else if (arr[_row*col + _col] < n)
{
_row++;
}
else
{
flag = true;
return flag;
}
}
}
return flag;
}
int main()
{
int arr[4][4] = { { 1, 2, 8, 9 }, { 2, 4, 9, 12 }, { 4, 7, 10, 13 }, { 6, 8, 11, 15 } };
bool ret=find((int *)arr, 4, 4, 7);//
cout << boolalpha << ret<<endl;//boolapha使返回值變成true輸出
return 0;
}
免責聲明:本站發(fā)布的內容(圖片、視頻和文字)以原創(chuàng)、轉載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內容。