数据结构与算法--数组：二维数组中查找

╰+攻爆jí腚メ 2022-11-21 04:21 185阅读 0赞

#### 数组 ####

*  数组最简单的是数据结构，占据一整块连续的内存并按照顺序存储数据，创建数组时候，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个元素，亚需要为所有数据预先分配内存，因此空间使用效率差，经常会有空闲区域没有得到充分利用。
 *  由于数组中内存是连续的，于是可以根据下标在O(1)时间内读/写任何元素，因此时间效率很高。
 *  为解决数组空间效率问题，人们设计实现了多种动态数组，Java中的vector。为了避免浪，我们先为数组开辟一个较小的空间，然后向数组添加元素的过程中，当元素个数超过数组容量的时候，我们会重新分配一个更大的空间，接着吧之前的数据复制到新的驻足中，在将之前的内存释放，这样就能减少内存的浪费。但是每一层扩充数组容量都有大量的额外操作，这多时间性能有负面的影响，因此使用动态数组时候要尽量减少改变数组容量大小的次数。

#### 算法题：二维数组中查找 ####

*  题目：在一个二维数组中，每一行从左到右递增顺序存储，每一列都按照从上到下递增顺序排序。完成一个函数，输入这样一个二维数组和一个整数，输出数组中是否包含改整数以及改整数的位置。
 *  分析过程如下： 例如下面二维数组，每行，列都递增。如果这个数组中查找数字6，则返回true，位置（2,1）。如果查找数字5返回false

1 2 3 4 5  
2 4 6 8 10  
3 6 9 12 15  
4 8 12 16 20

##### 错误解法分析过程如下 #####

*  按照题目要求，每列，行都递增，如上，通过观察以上矩阵的特性，很多同学会采用二分法，步骤如下：
    
     *  将二维数组看成是一个现象的结构，总共有20个元素，left=0，right=20， mid= (left+right)/2=10
     *  取中间位置元素值value与目标元素key比较
     *  value == key 则得出结果
     *  value < key则left = mid + 1
     *  value > key 则right = mid - 1
     *  具体实现如下

/** * 错误案例 * @author liaojiamin * @Date:Created in 13:59 2020/10/30 */
    public class FindOne { 
        public static Integer[][] getTwoDimenArray(int rows, int cloumns){ 
            Integer[][] twoDimen = new Integer[rows][cloumns];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cloumns; j++) { 
                    Integer key = (i+1) * (j+1);
                    twoDimen[i][j] = key;
                    System.out.print(key + " ");
                }
                System.out.println("");
            }
            return twoDimen;
        }
    
        public static void findOneInTwoDimenArray1(int rows, int cloumns, Integer key){ 
            if(rows <=0 || cloumns <=0){ 
                return;
            }
            Integer[][] twoDimen = getTwoDimenArray(rows, cloumns);
            if(twoDimen == null){ 
                return;
            }
            boolean isInArray = false;
            int keyCloumns = -1;
            int keyRows = -1;
    
            int left = 0;
            int right = rows * cloumns -1;
            int col = cloumns;
            while (left <= right){ 
                int mid = (left + right) / 2;
                Integer value = twoDimen[mid/ col][mid%col];//中间位置
                if(value == key){ 
                    keyRows = mid/col;
                    keyCloumns = mid%col;
                    isInArray = true;
                    break;
                }else if(value < key){ 
                    left = mid + 1;
                }else { 
                    right = mid - 1;
                }
            }
            System.out.println("isInArray: "+ isInArray + " position: rows:" +keyRows + " cloums:" + keyCloumns);
        }
    
        public static void main(String[] args) { 
            findOneInTwoDimenArray1(4, 5, 8);
        }
    }

*  以下测试案例：

//测试一：正确
    inPut:4,5,8
    outPut:
    1  2  3  4  5  
    2  4  6  8  10  
    3  6  9  12  15  
    4  8  12  16  20  
    isInArray: true  position: rows:1 cloums:3
    //测试二：错误
    input:5,4,8
    1  2  3  4  
    2  4  6  8  
    3  6  9  12  
    4  8  12  16  
    5  10  15  20  
    isInArray: false  position: rows:-1 cloums:-1

*  如上测试用例可知，以上解法是错误的，**原因在于虽然此二维数组每一列每一行都递增，当并不代表中间元素mid之前的元素一定小于mid**导致程序出错。

##### 正确解法分析过程如下 #####

*  还是将二维数组看成矩阵，，从中选一个元素 m与目标值key比较，分三种情况分析查找，
    
     *  情况一 当 m == key，结束查找
     *  情况二 当 m < key，根据数组排序规则，要查找的数字应该在当前选区的位置的右边或者下面  
        ![在这里插入图片描述][20201030171956376.png_pic_center]
     *  情况三 当m > key，同样的，要查的数字应该在左边或者上面  
        ![在这里插入图片描述][20201030172020966.png_pic_center]  
        ![在这里插入图片描述][20201030172629623.png_pic_center]
 *  如上分析，由于需要朝招的数字相对当前选取的m的位置有可能两个区域，而且有重叠，这样看起来就复杂了。
 *  我们将问题具体化，。下面以上图中矩阵中查找数字7 为案例，一步步分析查找过程。
 *  之前之所以困难，是我们在二维数组的中间选取的数字m 与目标值key比较，这样导致下一次需要查找的两个相互重叠的区域。如果我们从数组的一个角上选取，情况如下：
    
     *  首先选右上角数字9， 9 > 7，并且9 还在第四列的第一个数字，所有，7 不可能在第四列  
        ![在这里插入图片描述][20201030173613127.png_pic_center]
     *  将剩下三列看成一个新的二维数组，同样选右上角 8 > 7 ，同样可以排除第三列数  
        ![在这里插入图片描述][20201030173622109.png_pic_center]
     *  将剩下两列看成一个新二维数组，同样选右上角2 < 7，那么要查找的7 可能在2的右边也可能在2 的下面，因为之前的操作已经将右边的所有数据都排除了，所有必定在2 的下面，并且将2 这一行踢出，只剩下3\*2 的二维数组，如下  
        ![在这里插入图片描述][20201030173407351.png_pic_center]
     *  剩下上图中，同样用这个方法，去右上角4 < 7 ，所以不再这一行，可能在4下面，剩下2\*2 的二维数组  
        ![在这里插入图片描述][20201030173508602.png_pic_center]
 *  接着在取右上角 7 = 7 得出最终答案。

##### 总结 #####

*  以上查找过程，有如下规律：首先选取数组中右上角元素，
    
     *  如果改数字等于要查找数字，结束查找
     *  如果改数字小于要查找数字，踢出这个数字所在行
     *  如果这个数字大于要查找的数字，踢出这个数字所在的列
     *  依次每一步都在查找范围内踢出一列或者一行，逐步缩小范围。直到查询到或者为空。
     *  如下代码实现。
     *  时间复杂度 O(max(rows, cloumns))，空间复杂度 O(1)

/** * * @author liaojiamin * @Date:Created in 13:59 2020/10/30 */
    public class FindOne { 
        public static Integer[][] getTwoDimenArray(int rows, int cloumns){ 
            Integer[][] twoDimen = new Integer[rows][cloumns];
            for (int i = 0; i < rows; i++) { 
                for (int j = 0; j < cloumns; j++) { 
                    Integer key = (i+1) * (j+1);
                    twoDimen[i][j] = key;
                    System.out.print(key + " ");
                }
                System.out.println("");
            }
            return twoDimen;
        }
    
        public static void findOneInTwoDimenArray2(int rows, int cloumns, Integer key){ 
            if(rows <=0 || cloumns <=0 || key == null){ 
                return;
            }
            Integer[][] twoDimen = getTwoDimenArray(rows, cloumns);
            if(twoDimen == null){ 
                return;
            }
            boolean isInArray = false;
            int keyCloumns = cloumns -1;
            int keyRows =0;
            while (keyCloumns >= 0 && keyRows < rows){ 
                if(twoDimen[keyRows][keyCloumns] == key){ 
                    System.out.println("isInArray: "+ isInArray + " position: rows:" +keyRows + " cloums:" + keyCloumns);
                    break;
                }else if(twoDimen[keyRows][keyCloumns] > key){ 
                    keyCloumns --;
                }else { 
                    keyRows ++;
                }
            }
        }
        
        public static void main(String[] args) { 
            findOneInTwoDimenArray2(5, 4, 8);
        }
    }

*  测试用例：
    
     *  二维数组中查找包含的数字，数组中最大值，最小值，介于最大最小之间的值
     *  二维数组中查找不包含的数字，大于最大值，小于最小值，介于最大最小之前的不存在的值
     *  特殊输入 null

##### 其他思路 #####

*  以上是去右上角的数字，统一，可以选左下角的数字，
 *  不能选左上角的数字，例如选择1， 1 < 7 ，那么7 位于1 的下面或者右边，没有参考意义。
 *  不能选右下角的数字，例如15 , 15 > 7，那么7 位于15 的上面或者左边，没有参考意义。

[上一篇 数据结构与算法–实现Singleton模式][_Singleton]  
[下一篇：数据结构与算法–字符串：字符串替换][Link 1]

[20201030171956376.png_pic_center]: /images/20221120/370d922a10e04bc6832e4869ca320d83.png
[20201030172020966.png_pic_center]: /images/20221120/de9ae3616da84c5f85999c6e26b4e068.png
[20201030172629623.png_pic_center]: /images/20221120/8c823c2180414164a7eb1155d15f3a61.png
[20201030173613127.png_pic_center]: /images/20221120/f94c23502e6f4dd1bb704ebb480d4f01.png
[20201030173622109.png_pic_center]: /images/20221120/7f2c70a37feb469aa26be2b5e26cf0c7.png
[20201030173407351.png_pic_center]: /images/20221120/b7f6a1556c484e68a9f6b81d3e4512c9.png
[20201030173508602.png_pic_center]: /images/20221120/2c03c90654454077a1ebff2aecdb8c01.png
[_Singleton]: https://blog.csdn.net/liaojiamin0102/article/details/109314286
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/109478169