在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
首先想到用了一个二分查找,代码如下:
class Solution { public: bool Find(int target, vector<vector<int> > array) { int row = array.size(); if (row == 0) return false; int col = array[0].size(); if (col == 0) return false; for (int i=0; i<row; i++) { if (array[i].back() < target) continue; int left = 0; int right = col-1; int mid = 0; while(left<=right) { mid = left + (right-left)/2; if (array[i][mid] == target) return true; else if (array[i][mid] < target) left = mid + 1; else if (array[i][mid] > target) right = mid - 1; } } return false; } };
之后看答案发现还有更好的解法,从右上角开始找,如果找到了就返回,小于target就跳到下一行,如果大于target就跳到左边一列,按照这个思路又写了一遍:
class Solution { public: bool Find(int target, vector<vector<int> > array) { int row = array.size(); if (row == 0) return false; int col = array[0].size(); if (col == 0) return false; int row_index = 0; int col_index = col-1; while (row_index < row && col_index >=0) { if (array[row_index][col_index] == target) { return true; } else if (array[row_index][col_index] > target) { col_index--; } else if (array[row_index][col_index] < target) { row_index++; } } return false; } };