剑指offer [01]二维数组的查找
C++
方法一:
每行查找,每一行从右向左查找。若array[i][j]大于target,则进入下一行。
bool Find_1(int target, vector<vector<int> > array) { if (array.empty()|| array[0].empty()) return false; int row = array.size(); int col = array[0].size(); if (target<array[0][0] || target>array[row - 1][col - 1]) return false; for (int i = 0; i < row; i++) { if (array[i].empty()) continue; else if (target >= array[i][0]) { if (target <= array[i][array[i].size() - 1]) { for (int j = array[i].size() - 1; j >= 0; j--) { if (target == array[i][j]) { cout << "行:"<< i <<" "<< "列:" << j<<endl; return true; } else if (target > array[i][j]) break; } } else { continue; } } else return false; } }
方法二:
每行查找,把每一行看成有序递增的数组,利用二分查找,通过遍历每一行得到答案。
bool Find_2(int target, vector<vector<int> > array) { int row = array.size(); for (int i = 0; i < row; i++) { int low = 0; int high = array[i].size() - 1; while (low <= high) { int mid = (low + high) / 2; if (target > array[i][mid]) low = mid + 1; else if (target < array[i][mid]) high = mid - 1; else { cout << "行:" << i << " " << "列:" << mid << endl; return true; } } } return false; }
方法三:
利用二维数组由上到下,由左到右递增的规律,那么选取右上角或者左下角的元素a[row][col]与target进行比较,当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,即col--;当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,即row++;
bool Find_3(int target, vector<vector<int> > array) { int row = 0; int col = array[0].size() - 1; while (row <= array.size() - 1 && col >= 0) { if (target == array[row][col]) { cout << "行:" << row << " " << "列:" << col << endl; return true; } else if (target > array[row][col]) row++; else col--; } return false; }
python
方法一:
按行直接查找
class Solution: def Find(self, target, array): n = len(array) for i in range(n): if target in array[i]: return True return False
方法二:
(同C++方法三)
class Solution: def Find(self, target, array): # write code here rows = len(array) - 1 cols= len(array[0]) - 1 i = rows j = 0 while j<=cols and i>=0: if target<array[i][j]: i -= 1 elif target>array[i][j]: j += 1 else: return True return False