74. Search a 2D Matrix
整个二维数组是有序排列的,可以把这个想象成一个有序的一维数组,然后用二分找中间值就好了。
这个时候需要将全部的长度转换为相应的坐标,/col获得x坐标,%col获得y坐标
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int row = matrix.size(); if(row <= 0) return false; int col = matrix[0].size(); if(col <= 0) return false; int start = 0; int end = row*col - 1; int mid; while(start + 1 < end){ mid = start + (end - start)/2; int r = mid/col; int c = mid%col; if(matrix[r][c] == target) return true; else if(matrix[r][c] < target) start = mid; else end = mid; } if(matrix[start/col][start%col] == target) return true; if(matrix[end/col][end%col] == target) return true; return false; } };
240. Search a 2D Matrix II
与第一个题不同,行与行之间不是严格递增。剑指上的原题,从最左下角或者最右上角都可以
class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if(m <= 0) return false; int n = matrix[0].size(); if(n <= 0) return false; int i = 0,j = n-1; while( i < m && j >= 0){ if(matrix[i][j] == target) return true; else if(matrix[i][j] > target) j--; else i++; } return false; } };