在二维数组中查找
作者:bin题目:在一个二维数组中,每一行都按照从左到右递增顺序排序,每一列都按照从上往下递增排序,请完成一个函数,出入这样一个二维数据,和一个整数,判断数组中是否含有该整数
解题思路:
例如下面都一个二维数组,我们要寻找整数7
1 2 8 9
2 4 9 12
4 7 10 13
5 8 11 15
1 2 8 9
2 4 9 12
4 7 10 13
5 8 11 15
最笨都方法就是逐一进行比较,那样复杂度是O(n),其实因为数组从左至右,自上而下是递增都,所以我们可以从边缘开始判断,例如从9开始判断,9>7,所以9那一列就可以干掉
1 2 8 9
2 4 9 12
4 7 10 13
5 8 11 15
沿着这个思路记录,直到发现8>7,所以8那一列就可以干掉,如此一直朝着左或者下方向移动,例如要找出7数组,只要循环4次即可
java代码如下:
@Test public void ttt(){ int[][] nums = {{1,2,4,6},{2,4,7,8},{8,9,10,11},{9,12,13,15}}; int[] result = find(nums, -1); System.out.println(result[0]); System.out.println(result[1]); } public int[] find(int[][] nums, int num){ int rowIndex = nums.length - 1; int columnIndex = 0; int[] result = {-1, -1}; //脱离数组,超过到最底端或最左侧,即未找到 while (rowIndex >= 0 && columnIndex < nums[rowIndex].length - 1){ if (nums[rowIndex][columnIndex] == num){ result[0] = rowIndex; result[1] = columnIndex; break; } if(nums[rowIndex][columnIndex] > num){ //输入数字 < 数组中当前位置都数组,说明往下走没有意义列,尝试往左走 rowIndex--; }else { //往下走 columnIndex++; } }; return result; }