劍指offer 面試題 二維數組中的查找
送出網址： http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154
參與人數：11920 時間限制：1秒 空間限制：32768K
本題知識點：查找
題目描述
在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。
輸入描述:
array： 待查找的二維數組
target：查找的數字
輸出描述:
查找到傳回true，查找不到傳回false
分析：
如果矩陣右上角的值比target大，删除所在的列，列号-1，在剩下的元素中繼續找；如果矩陣右上角的值不大于target，删除所在的行，行号+1，在剩下的元素中繼續找，找到相等的元素就退出.
由于線上oj給的C++版輸入是向量，故不能直接使用C語言風格的二維數組展開為一維的方法。
AC代碼:
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool Find(vector<vector<int> > array, int target) {
int rows=array.size(); // 行數
int cols=array[0].size(); // 列數
int i=0, j=cols-1;
bool found = false;
while(j>=0 && j<cols && i<rows) // i>=0 預設滿足，無須再判斷
{
if(array[i][j] == target) { found = true; break; }
else if(array[i][j] > target) j--; // 如果矩陣右上角的值比target大，删除所在的列，列号-1
else i++; // 如果矩陣右上角的值不大于target，删除所在的行，行号+1
}
return found;
}
};
// 以下為測試部分
/*
int main()
{
Solution sol;
int i,j;
vector<vector<int> > arr(5, vector<int>(3));
for (i = 0; i < arr.size(); i++)
for (j = 0; j < arr[0].size(); j++)
arr[i][j] = 2*i*j;
cout<<sol.Find(arr,4)<<endl;
vector<vector<int> > matrix = {
{1,4,7,11,15},
{2,5,8,12,19},
{3,6,9,16,22},
{10,13,14,17,24},
{18,21,23,26,30}
};
int target = 30;
cout<<sol.Find(matrix,target)<<endl;
return 0;
}
*/ 複制
leetcode 74. Search a 2D Matrix
Total Accepted: 79103 Total Submissions: 233263 Difficulty: Medium
送出網址： https://leetcode.com/problems/search-a-2d-matrix/
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
- Integers in each row are sorted from left to right.
- The first integer of each row is greater than the last integer of the previous row.
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
] 複制
Given target =
3
, return
true
.
Leetcode AC代碼：
#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int rows=matrix.size(); // 行數
int cols=matrix[0].size(); // 列數
int i=0, j=cols-1;
bool found = false;
while(j>=0 && j<cols && i<rows) // i>=0 預設滿足，無須再判斷
{
if(matrix[i][j] == target) { found = true; break; }
else if(matrix[i][j] > target) j--; // 如果矩陣右上角的值比target大，删除所在的列，列号-1
else i++; // 如果矩陣右上角的值不大于target，删除所在的行，行号+1
}
return found;
}
};
int main()
{
Solution sol;
vector<vector<int>> vec1={{1}};
vector<vector<int>> vec2=
{
{1, 3, 5, 7},
{10, 11, 16, 20},
{23, 30, 34, 50}
};
int res1 = sol.searchMatrix(vec1, 2);
int res2 = sol.searchMatrix(vec2, 3);
printf("%d\n", res1);
printf("%d\n", res2);
return 0;
} 複制