LeetCode—剑指Offer：二维数组中的查找（暴力）
剑指Offer：二维数组中的查找（简单）
2020年8月8日
解题
-
暴力
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//拿到行数
int n_len=matrix.length;
//处理异常值
if(n_len==0) return false;
//拿到列数
int m_len=matrix[0].length;
//处理异常值
if(m_len==0) return false;
//在第一行找到第一个比目标数大的数，这个数往后肯定都比目标数大，如果没有比目标数大的，就取列数
//定义矩阵第一行比目标数大的数的列数
int column_num=m_len;
for(int i=0;i<m_len;i++){
if(matrix[0][i]>target){
column_num=i;
}
}
//同上道理，取行数
//定义矩阵第一列比目标数大的数的行数
int row_num=n_len;
for(int i=0;i<n_len;i++){
if(matrix[i][0]>target){
row_num=i;
}
}
//在该范围区间内找数，找到就返回true，遍历完没找到就返回false
for(int i=0;i<row_num;i++){
for(int j=0;j<column_num;j++){
if(matrix[i][j]==target){
return true;
}
}
}
return false;
}
}
-
暴力plus
在每一行的范围最大列进行判断，如果比目标数小就跳过，进入下一行的判断
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
//拿到行数
int n_len=matrix.length;
//处理异常值
if(n_len==0) return false;
//拿到列数
int m_len=matrix[0].length;
//处理异常值
if(m_len==0) return false;
//在第一行找到第一个比目标数大的数，这个数往后肯定都比目标数大，如果没有比目标数大的，就取列数
//定义矩阵第一行比目标数大的数的列数
int column_num=m_len;
for(int i=0;i<m_len;i++){
if(matrix[0][i]>target){
column_num=i;
}
}
//同上道理，取行数
//定义矩阵第一列比目标数大的数的行数
int row_num=n_len;
for(int i=0;i<n_len;i++){
if(matrix[i][0]>target){
row_num=i;
}
}
//在该范围区间内找数，找到就返回true，遍历完没找到就返回false
for(int i=0;i<row_num;i++){
//如果这行的范围列数比目标值小就跳过
if(matrix[i][column_num-1<0?column_num:column_num-1]<target){
continue;
}
for(int j=0;j<column_num;j++){
if(matrix[i][j]==target){
return true;
}
}
}
return false;
}
}
-
暴力plusplus
先以矩阵左下角和第一行第一列的数作为标志，如果比左下角的数小，那么就到上一行进行对比，如果比左下角的数大，那就到下一列进行对比。如果出界，则证明无目标数存在。
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int i = matrix.length - 1, j = 0;
while(i >= 0 && j < matrix[0].length)
{
if(matrix[i][j] > target) i--;
else if(matrix[i][j] < target) j++;
else return true;
}
return false;
}
}