Problem 3：二维数组中的查找

王晗发布于2019-08-16 14:16 / 431人阅读

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

一、题目描述

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

二、思路分析

首先分析该数组的特点，在向下和向右方向上，数值会递增。以二维数组中任意位置元素为例，同行右侧元素皆大于该点，同列下侧元素皆大于该点，因此该点右下侧元素皆大于该点。

而右上侧和左下侧点都可能有大于该点的点，初步可认为，大于该值的点位于右侧和下侧。
因此，我们可以根据该数组的特点进行逐行剔除，达到缩小范围，查找目标值的目的。

算法思路

首先确定初始点，由于剔除某行/列，需要与目标值对比。初始点大于目标值，需要往小侧移动；初始点小于目标值，需要往大侧移动。而四个顶点，只有左下角和右下角，进行横向和纵向移动能高效筛选和剔除行列。

选择右上角为初始点，执行下述操作
1）如果该点等于目标值，结束查找
2）如果该点小于目标值，往大侧移动，下移一行（列索引不变）
3）如果该点大于目标值，往小侧移动，左移一列（行索引不变）
重复上述过程，直到索引超过数组边界。如果符合1，退出重复。这里，我们认为本题找到目标值即可，无需查找是否有其他位置的目标值。

根据上述思路，通过向左下移动，达到整行或者整列的剔除，实现比较快速的查找。可以把这个过程理解为剥洋葱，一层层剥开外层的非目标层，查找内部的目标值。

三、Java实现

源程序：

package jz_offer;

public class problem03
{
    /**
     * -查找二维数据arr中是否存在数值num
     * @param   arr：二维数组
     *            num：目标值
     * @return  在二维数组中是否找到了目标值num，返回类型boolean
     */
    public static boolean findNum(int[][] arr,int num){
        boolean flag=false;  //标志位，为true时表示找到目标值
        int i=0;
        int j=arr[0].length-1;
        while(flag!=true&&i=0){
            if(arr[i][j]==num){
                flag = true;
                break;
            }else if(arr[i][j]

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72889.html

LintCode547/548_求数组交集不同解法小结

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法 LintCode547/548_求数组交集不同解法小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segme...

gxyz 2019-08-16 10:34 评论0 收藏0
Java编程基础06——数组

摘要：空指针异常原因数组已经不在指向堆内存了。当访问数组不存在的索引时，就会出现数组索引越界异常数组的操作遍历掌握案例演示数组遍历就是依次输出数组中的每一个元素。内循环控制的是一维数组的长度。 1.数组概述和定义格式说明 A:为什么要有数组(容器)：为了存储同种数据类型的多个值 B:数组概念：数组是存储同一种数据类型多个元素的集合。也可以看成是一个容器；数组既可以存储基本数据类型，也可...

荆兆峰 2019-08-19 11:04 评论0 收藏0
【刷算法】二维数组中的查找

摘要：题目描述在一个二维数组中每个一维数组的长度相同，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。分析例如二维数组，，如果按照常规的查找，从开始，那么，和都大于，接下来该怎么办呢这就陷入了一个无法进行下去的局面。题目描述在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的...

Worktile 2019-08-23 10:22 评论0 收藏0
java知识体系梳理-->数组

摘要：知识体系梳理流程图一维数组数组概述数组是指一组数据的集合，数组中的每个数据被称作元素。定义打印数组元素方法按照给定的格式打印题目分析通过观察发现，要实现按照指定格式，打印数组元素操作。按照这种方式，数组循环多圈以后，就完成了数组元素的排序。知识体系梳理流程图 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一维数组 ...

james 2019-08-15 12:23 评论0 收藏0
【LC总结】Iterator题目<Zigzag 1&2><BST>&

摘要：方法直接查找数组的位的迭代器，调用方法得到的整数即为要返回的元素。再写迭代器的方法返回指针元素的并让指针通过递归方法指向下一个元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

WelliJhon 2019-08-14 15:49 评论0 收藏0