精华内容
下载资源
问答
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 题目...

    剑指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.题目描述

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

     题目分析:

    1. 每一行都是从左至右递增的顺序排序,是有顺序的,可以使用查找算法:二分查找
    2. 二维数组的每一行的第几个,可以表示为,a[i].length,表示的是第i行的长度
    3. 对每行的数组元素二分查找
    4. 得到的结果进行判断,得出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.总结

    1. 二维数组对元素的查找,转化成在一维数组中查找元素,使用查找方法
    2. 最近课挺多的,时间上有点紧张
    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

    展开全文
  • 空二维数组的长度

    2019-04-19 21:18:39
    今天在做剑offer第题:二维数组的查找时,实现从左下来查找时竟然报出数组越界错误,但是仔细看代码和右上查找时几乎相同。 报错例子是一个二维空数组,我输出它的列长度和行长度才觉得这件事不简单。 对于个...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 示例: ...
  • 1:一维数组: int a[5]; &a数组的地址,故&a + 1加一个数组大小的长度。增加20个字节。 p2=&a 由于p2指向具有10个整型元素数组的指针,所以p2+1所指向的下一个元素,所以p2+1所的下一...对一维数组的地址取
  • ❝永远要这样写代码,好像最终维护你代码的人个狂暴的、知道你住在哪里的精神病患者—— 小浩算法❞二维数组中的查找题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每...
  • 小编在求职找找工作期间剑offer上的算法题刷了很多遍...下面第056道剑offer算法题:题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺...
  • 维数组的长度.length

    2016-03-01 14:49:09
    1; num[0][1] = 1;//给第行第二个元素...//二维数组对象时,length所代表的长度 //数组名后直接加上length,所有几行 //指定索引后加上length(如arr[0].length),该行所拥有的元素,列的数目[/code]
  • 二维数组中的查找信息卡片时间:2020-03-16题目:二维数组中的查找tag:search array题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序...
  • ❝永远要这样写代码,好像最终维护你代码的人个狂暴的、知道你住在哪里的精神病患者—— 小浩算法❞二维数组中的查找题目描述在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每...
  • 题目描述:在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数...
  • 一维数组保存一组数据类型相同的数据声明一个数组: 数据类型[ ] 数组名 = 初值注意: 这里的数据类型数组中保存数据的类型声明方式一: int array = new int[数组的长度];注意: 数组的长度一旦确定 就不能...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。public ...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 解法一...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。 请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路:...
  • C语言一维数组的定义与常见用法

    千次阅读 2020-05-07 16:54:48
    在上述语法格式中,类型说明符表示数组中所有元素的类型,常量表达式是数组的长度,也就是数组中存放元素的个数。 例 int array[5l; 上述代码定义了个数组,其中,int数组的类型,aray数组的...
  • 时间限制:1秒 空间限制:32768K在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路: ...
  • 多维数组的概念首先说说多维数组的概念。多维数组在不同语言中有大同小异的语法定义,但是逻辑定义上基本上一致,就是同数据类型、同逻辑含义的数据单元构成的能够用整数为坐标访问的超立方体的数据集合。这里我用的...
  • 5.1.1 一维数组

    2020-06-27 13:18:40
    5.1.1 一维数组 数组是指一组类似个数组组成集合,集中表示有利于管理。如一个班所有同学可以用一个数组表示,同学1代表张三,同学2代表李四…… 本节介绍一维数组。 语法: [数据类型] 数组名[数组长度]; ...
  • 如何获取二维数组元素个数呢?int[,] array = new int[,] {{1,2,3},{4,5,6},{7,8,9}};//定义一个3行3列维数组 int row = array.Rank;//获取维数,这里行数...(0一维,1表示的是第二维) int col = ar...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路: ...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路...
  • 题目描述:在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数...
  • 答:其实二维数组相当于由一维数组构成的数组。如果想存放若干行长长短短不一样的信息时,用二维数组就不方便了。因为二维数组规定每一行的列的长度是一样的。例6-8 利用指针数组存放矩阵#include <iostream&...
  •  在一个二维数组中(每个一维数组的长度相同),  每一行都按照从左到右递增的顺序排序,  每一列都按照从上到下递增的顺序排序。  请完成一个函数,输入这样的一个二维数组和一个整数,  判断数组中是否含有该...
  • 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。 思路...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 861
精华内容 344
关键字:

一维数组的长度是指