这道题目是昨天牛客网远程面试的第二道算法题。
题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
很遗憾，这道题面试时我根本没有想出答案来。
面试官：你先想一种最简单的方法出来，然后再慢慢优化。
我：因为横向和纵向都是递增的，所以大概可以用二分查找之类的吧。然而，我也没想出具体解法来。。。
面试官：其实，最简单的方法就是从前向后依次遍历这个二维数组进行查找
我：。。。
然后面试就跪了吧！面试官最终也没有说具体解答，现在面试完了就再自己想一想吧！首先，那就先写个最简单的方法然后再考虑优化吧。
简单粗暴
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println(s.find(arr, 7));
}
/**
* 二维数组中查找目标值是否存在
*
* @param arr 二维数组
* @param target 目标值
* @return 存在则返回 true，否则 false
*/
public boolean find(int[][] arr, int target) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
if (arr[i][j] == target) {
return true;
}
}
}
return false;
}
}
但是这种方法效率肯定是最差的，所以还是考虑下优化吧！
想了半天又是没想出来，于是百度之。才发现这原来是剑指Offer上面的原题呢，看了这位老哥的博客：http://blog.csdn.net/shakespeare001/article/details/51280467。下面我也学着写下这位老哥的解答吧！
[山代王] 思路一
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println(s.optFind(arr, 7));
System.out.println(s.optFind(arr, 2));
System.out.println(s.optFind(arr, 12));
}
/**
* 二维数组中查找目标值是否存在-优化版
*
* @param arr 二维数组
* @param target 目标值
* @return 存在则返回 true，否则 false
*/
public boolean optFind(int[][] arr, int target) {
int rows = arr.length;
int cols = arr[0].length;
int i = rows - 1;
int j = 0;
while (i >= 0 && j < cols) {
if (arr[i][j] > target) {
i--;
} else if (arr[i][j] < target) {
j++;
} else {
return true;
}
}
return false;
}
}
这个解法个人感觉跟算法关系不是特别大，倒是像是考察看图找规律的题目了。。。
[山代王] 思路二
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println(s.optFind2(arr, 7));
System.out.println(s.optFind2(arr, 2));
System.out.println(s.optFind2(arr, 12));
}
/**
* 二维数组中查找目标值是否存在-优化版2
*
* @param arr 二维数组
* @param target 目标值
* @return 存在则返回 true，否则 false
*/
public boolean optFind2(int[][] arr, int target) {
int low, mid, high;
for (int i = 0; i < arr.length; i++) {
low = i;
high = arr.length - 1;
mid = (low + high) / 2;
while (low <= high) {
if (arr[mid][i] == target) {
return true;
}
if (arr[mid][i] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
mid = (low + high) / 2;
}
}
for (int i = 0; i < arr.length; i++) {
low = i + 1;
high = arr[i].length - 1;
mid = (low + high) / 2;
while (low <= high) {
if (arr[i][mid] == target) {
return true;
}
if (arr[i][mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
mid = (low + high) / 2;
}
}
return false;
}
}
思路二就是利用二分查找来进行查找了，这里【山代王】的做法是先把二维数组分为两个三角形再分别做二分查找。然而我没想明白为啥不简单的直接一行一行的做二分查找，就正如下面我的实现。
我的二分查找
/**
* Created by clearbug on 2018/2/26.
*/
public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int[][] arr = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
System.out.println(s.optFind3(arr, 7));
System.out.println(s.optFind3(arr, 2));
System.out.println(s.optFind3(arr, 12));
}
/**
* 二维数组中查找目标值是否存在-优化版3
*
* @param arr 二维数组
* @param target 目标值
* @return 存在则返回 true，否则 false
*/
public boolean optFind3(int[][] arr, int target) {
int low, mid, high;
for (int i = 0; i < arr.length; i++) {
low = 0;
high = arr[i].length - 1;
mid = (low + high) / 2;
while (low <= high) {
if (arr[i][mid] == target) {
return true;
}
if (arr[i][mid] > target) {
high = mid - 1;
}
if (arr[i][mid] < target) {
low = mid + 1;
}
mid = (low + high) / 2;
}
}
return false;
}
}