剑指offer算法题


查找 数组

题目描述

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

方法一

通过这个数组的规律我们可以发现，数组每一列从下往上是递减的，每一行从左往右是递增的。因次我们可以从左下角的那个数开始比较，如果目标数大于左下角的数，则往右找；如果目标数小于左下角的数，则往上找。

下面是Java代码
public class Solution {
    public boolean Find(int target, int [][] array) {
        int len = array.length-1;
        int width = 0;
        while( len>=0&& width < array[0].length){
            if(target == array[len][width]){
                return true;
            }else if(target > array[len][width]){
                width++;
            }else if(target < array[len][width]){
                len--;
            }
            
        }
        return false;
    }
}

方法二 二分查找

针对数组每一行进行二分查找。同时，由于每一行自左至右是递增的，所以每一行最右遍的那个数是最大的。为了提高效率，我们可以在二分查找前使用target和最右边的数字进行比较，如果目标数大，则肯定不在此行，所以直接继续循环，进行下一行判断。
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array[0].length == 0){
            return false;
        }
        int len = array.length-1;
        int widthMax = array[0].length;
        
        for(int i = 0 ; i <=len ; i++){
            int high = widthMax-1;
            int low = 0;
            if(target > array[i][high]){
                continue;
            }
            while(low <= high){
                int mid = low + (high - low)/2;
                if(target > array[i][mid]){
                    low = mid+1;
                }else if(target < array[i][mid]){
                    high = mid-1;
                }else{
                    return true;
                }
            }
        }
        return false;
    }
}

参考https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&&tqId=11154&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

1.题目描述

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

 题目分析：

每一行都是从左至右递增的顺序排序，是有顺序的，可以使用查找算法：二分查找
	
二维数组的每一行的第几个，可以表示为，a[i].length,表示的是第i行的长度
	
对每行的数组元素二分查找
	
得到的结果进行判断，得出true或者false
2.代码实现

public class Solution {
    // 二位数组是从左到右递增，从上往下递增
    public boolean Find(int target, int [][] array) {
        /*
        每一行元素都是有序递增的数组，可以对每一行数组二分查找
        通过遍历每一行得到答案
        时间复杂度为nlogn
        */
        //对数组进行循环
        for(int i = 0;i < array.length;i++){
            int low = 0;
            int high = array[i].length - 1;
            while(low <= high){
                //取数组下标为中间元素
                int mid = (low + high) / 2;
                 
                if(target > array[i][mid]){
                    low = mid + 1;
                }else if(target < array[i][mid]){
                    high = mid - 1;
                }
                else{
                    return true;
                }
            }
             
        }
        return false;
    }
}

3.总结

二维数组对元素的查找，转化成在一维数组中查找元素，使用查找方法
	
最近课挺多的，时间上有点紧张
	
积累，坚持就是胜利！

题目描述

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

分析：

矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，因此从左下角开始查找，当要查找数字比左下角数字大时。右移要查找数字比左下角数字小时，上移。

实现代码：

public class Collection {
    public boolean Find(int target, int [][] array) {
        int c = 0;//第0列
        int r = array.length-1;//最后一行
        while((r>=0)&&(c<array[0].length)){//边界条件
            if(array[r][c]<target){//如果target大于array，则右移
                r++;
            }else if(array[r][c]>target){//如果target小于array，则上移
                c--;
            }else{
                return true;//满足等于就为true
            }
        }
        return false;//全都不满足，则为false。
    }
    public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		System.out.println("请输入数组行数和列数\n");
		int x = s.nextInt();
		int y = s.nextInt();
		int[][] array = new int[x][y];// 初始化数组
		System.out.println("请输入数组元素\n");
		for (int i = 0; i < x; i++)// 循环输入
			for (int j = 0; j < y; j++)
				array[i][j] = s.nextInt();
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入一个整数\n");
		int t = sc.nextInt();
		Find(t, array);
		if (Find(t, array) == false) {
			System.out.println("数组中不含该元素");
		} else
			System.out.println("数组中含有该元素");
	}
}

输出示例：

一、题目描述

　　在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 
二、思路解析
　　此问题使用类似于二分查找的算法。右上角元素（第一行最后一列）的元素是第一行元素与最后一列元素构成的递增序列的分割点，因为此元素的左面元素都比此元素小，此元素的下面元素都比此元素大（类似于二分查找中的中点位置的元素）。所以每次循环，比较目标元素target与右上角元素的大小关系，如果相等，则找到，返会true即可。如果target元素大于右上角元素，则target大于当前第一行所有元素，所以target不能出现在第一行，所以需要把第一行清除。如果target元素小于右上角元素，则target小于最后一列所有元素，不可能出现在最后一列，所以需要把最后一列清除。清除第一行或者最后一列之后，继续采用上述方法，用右上角元素与target元素进行比较。如果当列数减小到零或者行数增加到最后一行都没有找到target，则返回false，说明此二维数组中没有与target相同的元素

 
三、Java代码
　　
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;//获得初始行数
        int cols = array[0].length;//获得初始的列数

        boolean flag = false;//设置标志位为false
        int row = 0;//动态行数默认从0开始
        int col = cols-1;//动态列数默认从最后一列开始

        while(row<=rows-1 && col>=0){//当没有达到最后一行并且没有达到第一列的时候
            if(array[row][col] == target){//如果对象元素等于target，找到，break
                flag = true;
                break;
            }else if(array[row][col] < target){
                row++;
            }else{
                col--;
            }
        }
        return flag;
    }
}
以上均为个人理解，如果不正确、不合理或者可以优化的地方，欢迎下方留言。　








转载于:https://www.cnblogs.com/xwwbb/p/10732247.html