核心考點：陣列相關，特性觀察，時間復雜度把握
在一個二維陣列中（每個一維陣列的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序，請完成一個函式，輸入這樣一個二維陣列和一個整數，判斷陣列中是否含有該整數，
決議一：（不提倡）
這種在二維陣列當中進行查找的問題，很多人的思路就是依次遍歷二維陣列當中的元素進行查找，
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
for (int i = 0; i < array.size(); i++)
{
for (int j = 0; j < array[i].size(); j++)
{
if (target == array[i][j])
return true; //找到了回傳true
}
}
return false; //沒找到回傳false
}
};
決議二：（正解）
查找的程序本質上是排除的程序，若逐個遍歷二維陣列進行查找，那么我們一次只能排除一個元素，我們應該充分利用題目所給條件進行查找，
對此，我們可以讓待查找數字先與第一行最后一個元素進行比較（或是先于第一列最后一個元素比較，比較邏輯變一下即可），
若待查找數字比該元素大，則我們就無需再在第一行進行查找了，因為第一行的元素中最后一個元素最大，待查找元素比這個元素都大了，那必定比該行其他元素也大，
若待查找數字比該元素小，則我們就無需再在最后一列進行查找了，因為最后一列的元素中第一行的元素最小，待查找元素比這個元素還要小，那必定比該列其他元素也小，
這樣一來，經過一次判斷我們就可以排除一行或是一列元素，相比一次排除一個元素來說，那真是快了太多了，而經過一次判斷后，剩下的仍然是一個二維陣列，我們可以通過相同的方法對其再次進行判斷，直到找到這個元素或是將整個二維陣列遍歷結束，
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i = 0, j = array[0].size() - 1;
while (i < array.size() && j >= 0)
{
if (target > array[i][j]) //待查找數字比該元素大
{
i++; //無需在改行進行查找了
}
else if (target < array[i][j]) //待查找數字比該元素小
{
j--; //無需在該列進行查找了
}
else
{
return true; //找到了回傳true
}
}
return false; //陣列遍歷結束，未找到回傳false
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298154.html
標籤：其他