二维数组中的查找

基础知识

1 数组和字符串是两种最基本的数据结构，它们用连续内存分别存储数字和字符

2 栈是一个与递归紧密相关的数据结构，

3 队列也与广度优先遍历算法紧密相关，

4 数组可以说是最简单的一种数据结构，它占据一块连续的内存并按照顺序存储数据。创建数组时，我们需要首先指定数组的容量大小，然后根据大小分配内存。即使我们只在数组中存储一个数字，也需要为所有的数据预先分配内存。因此数组的空间效率不是很好，经常会有空闲的区域没有得到充分利用。

5 为了解决数组空间效率不高的问题，人们又设计实现了多种动态数组，比如C++的 STL中的vector。把之前的数据复制到新的数组中，再把之前的内存释放，这样就能减少内存的浪费。但我们也注意到每一次扩充数组容量时都有大量的额外操作，这对时间性能有负面影响，因此使用动态数组时要尽量减少改变数组容量大小的次数。

题目描述

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 

1、思路

首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

2、举例

如果在一个二维数组中找到数字7，则返回true，如果没有找到，则返回false。

 

查找过程如下：

方法2

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0)
            return false;
        
        int row = 0, col = matrix[0].length - 1;
        while (row < matrix.length && col >= 0) {
            if (target == matrix[row][col])
                return true;
            else if (target > matrix[row][col])
                row++;
            else
                col--;
        }
        return false;
    }
}

 

 

/**
 * @Auther: liuhaidong
 * Data: 2019/10/9 0009、22:00
 * Description:
 * @version: 1.0
 */
public class ArrayListTest {
    public static void main(String[] args) {
        int[][] arr = {
  {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
//        int[][] arr ={
  {1}};
        int a = 7;
        System.out.println(find(arr,a));
    }

    private static boolean find(int[][] arr, int a) {
        // 输入条件判断
        if (arr == null || arr.length < 1 || arr[0].length < 1) {
            return false;
        }

        for(int j = arr[0].length-1;j >= 0;j--){
            for(int i =0;i<=arr.length-1;i++){
                if(arr[i][j] > a){
                    break;
                }
                if(arr[i][j] < a){
                    continue;
                }
                if (arr[i][j] == a){
                    return true;
                }
            }
        }
        return false;
    }