面试题3-二维数组中的查找
基础知识
数组是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。在创建数组的时候，必须首先指定数组的容量大小，然后根据大小来分配内存，一经建立之后数组的大小便不能更改，这就造成了其空间利用的效率不够高。但是数组的内存是连续的，可以根据下标在O(1）的时间内读写任意的元素，因此它的时间效率很高。
在不同的编程语言中，都存在动态数组，如C++中的Vector，Java中的ArrayList。这些动态数组都有初始容量，当数据的数目超过数组的初始容量的时候，重新分配一块更大的空间，把之前的数据复制到新的数组中去，释放之前的内存，这样减少了内存的浪费。但是每一次的扩容都会有大量的额外操作，这会对时间性能造成影响，因此在使用动态数组的时候要尽量减少改变数组容量的次数。
题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成提个函数输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：
- 这道题暴力的解法是两层的循环逐一的查找，显然这种复杂度O(mn)的算法是不可取的。
- 可以在此基础之上进行改进，每一行使用二分查找的方法，减少查找的次数，那么复杂度就能下降到O(mlgn)。
- 首先比较二维数组右上角的数字，若和目标数据相等，查找结束，如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除该数字所在的行。这样一行一列的逐步缩小要查找的范围，最后找到数字或者范围为空。（仔细想想这种解法有点动归的意思）这种思想的算法复杂度最坏情况下为O(m+n)。算法还是很神奇的。
代码
二分：
- public class Solution {
- public boolean Find(int target, int [][] array) {
- if( array == null)
- return false;
-
- int row = array.length;
- //System.out.println(row);
- int col = array[0].length;
- boolean res = false;
- if(row > 0 && col >0){
- int min = array[0][0];
- int max = array[row-1][col-1];
- if(target < min || target > max)
- return false;
- //System.out.println("test");
- int i = 0;
-
- while( i < col){
- int low = 0,high = row - 1, mid = 0;
- while(low <= high){
- mid = low + (high - low)/2;
- if(target == array[i][mid]){
- res = true;
- return res;
- }
- if(target > array[i][mid]){
- low = mid + 1;
- }else{
- high = mid - 1;
- }
- }
- i ++;
- }
- }
- return res;
-
- }
- }
从右上删减行列减少范围：
- public class Solution {
- public boolean Find(int target, int [][] array) {
- int row = array.length;
- if(row == 0)
- return false;
- int col = array[0].length;
- int i = 0, j = col - 1;
- while(i < row && j >=0 ){
- if(target == array[i][j])
- return true;
- if(target > array[i][j])
- i++;
- else
- j--;
- }
- return false;
- }
- }