[剑指offer_04] 二维数组中查找目标值
[剑指offer_04] 二维数组中查找目标值
1. 二维数组中查找目标值
题目描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
思路:从右上角或左下角开始找,逐行排除,或者用逐行遍历+二分法查找
2. 右上角开始找
/** * 解法一:双指针(右上方开始找) * 时间复杂度:O(m*n),空间复杂度:O(1) * * @param array 二维数组 * @param target 目标值 * @return true:找到 false:未找到 */
public boolean Find1(int target, int [][] array) {
if(array == null && array.length == 0){
return false;
}
int row = 0; //行
int col = array[0].length - 1; //列
while(row < array.length && col >= 0) {
if(array[row][col] == target) {
//如果刚好等于target,返回true
return true;
}
if(array[row][col] > target) {
//如果该数字大于target,剔除所在列
col --; //列左移
}else{
//如果小于target,剔除所在行
row ++; //行下移
}
}
return false;
}
3. 左下角开始找
/** * 解法一:双指针(左下方开始找) * 时间复杂度:O(mn),空间复杂度:O(1) * * @param array 二维数组 * @param target 目标值 * @return true:找到 false:未找到 */
public static boolean find2(int[][] array, int target) {
if (array == null || array.length == 0) {
return false;
}
int row = array.length - 1; //行
int column = 0; //列
while (row >= 0 && column < array[0].length) {
if (array[row][column] == target) {
//如果刚好等于target,返回true
return true;
}
if (array[row][column] > target) {
row--; //行,目标小于当前值,往上找
} else {
column++; //列,目标比当前值大,往右边找
}
}
return false;
}
4. 逐行遍历+二分查找
/** * 解法二:二分法 * 时间复杂度:O(log m*n),空间复杂度:O(1) * * @param array 二维数组 * @param target 目标值 * @return true:找到 false:未找到 */
public static boolean find3(int[][] array, int target) {
//非空判断
if(array == null || array.length == 0){
return false;
}
for(int i = 0; i< array.length; i++) {
int left = 0;
int right = array[0].length - 1; //不要忘记减去1
//二分查找
while(left<=right) {
int mid = (left + right) / 2;
if(target == array[i][mid]){
return true;
}else if(target > array[i][mid]){
left = mid + 1;
}else{
right = mid - 1;
}
}
}
return false;
}
5. 测试用例
/** * 测试Test3 * * @author 周鹏飞 * @version 1.0 * @date 2020/3/28 15:10 */
public class Test3 {
@Test
public void test3() {
int[][] testArray = {
{
1, 7, 8, 9}, {
2, 4, 9, 12}, {
4, 7, 10, 13}, {
6, 8, 11, 15}};
int target = 1;//1,6,15
System.out.println("解法一:两个指针(右上),数组中是否含有" + target + " :" + FindNum3.find(testArray, target));
System.out.println("解法一:两个指针(左下),数组中是否含有" + target + " :" + FindNum3.find2(testArray, target));
System.out.println("解法二:二分法,数组中是否含有" + target + " :" + FindNum3.find3(testArray, target));
}
}