JZ01-二维数组中的查找
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
//双指针
class Solution3 {
public boolean Find(int target, int[][] array) {
int rows = array.length;
if (rows == 0) {
return false;
}
int cols = array[0].length;
if (cols == 0) {
return false;
}
int row = rows - 1;
int col = 0;
//边界控制
while (row >= 0 && col < cols) {
if (array[row][col] < target) {
col++; //去除不可能的，缩小范围，去除后不可能在该范围内
} else if (array[row][col] > target) {
row--;
} else {
return true;
}
}
return false;
}
}
//对每行使用折半查找
class Solution4 {
public boolean Find(int target, int[][] array) {
if (array == null || array.length == 0 || array[0].length == 0) {
return false;
}
int col = array[0].length;
for (int i = 0; i < array.length; i++) {
int min = 0;
int max = col - 1;
//折半查找
for (int j = 0; j < col; j++) {
int mid = (min + max) / 2;
int value = array[i][mid];
if (value == target) {
return true;
} else if (value < target) {
min = mid + 1;
} else {
max = mid - 1;
}
}
}
return false;
}
}
投递三一重工等公司7个岗位
