成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Problem 3：二維數(shù)組中的查找

王晗 / 473人閱讀

摘要：一題目描述在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

一、題目描述

在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

二、思路分析

首先分析該數(shù)組的特點(diǎn)，在向下和向右方向上，數(shù)值會遞增。以二維數(shù)組中任意位置元素為例，同行右側(cè)元素皆大于該點(diǎn)，同列下側(cè)元素皆大于該點(diǎn)，因此該點(diǎn)右下側(cè)元素皆大于該點(diǎn)。

而右上側(cè)和左下側(cè)點(diǎn)都可能有大于該點(diǎn)的點(diǎn)，初步可認(rèn)為，大于該值的點(diǎn)位于右側(cè)和下側(cè)。
因此，我們可以根據(jù)該數(shù)組的特點(diǎn)進(jìn)行逐行剔除，達(dá)到縮小范圍，查找目標(biāo)值的目的。

算法思路

首先確定初始點(diǎn)，由于剔除某行/列，需要與目標(biāo)值對比。初始點(diǎn)大于目標(biāo)值，需要往小側(cè)移動；初始點(diǎn)小于目標(biāo)值，需要往大側(cè)移動。而四個頂點(diǎn)，只有左下角和右下角，進(jìn)行橫向和縱向移動能高效篩選和剔除行列。

選擇右上角為初始點(diǎn)，執(zhí)行下述操作
1）如果該點(diǎn)等于目標(biāo)值，結(jié)束查找
2）如果該點(diǎn)小于目標(biāo)值，往大側(cè)移動，下移一行（列索引不變）
3）如果該點(diǎn)大于目標(biāo)值，往小側(cè)移動，左移一列（行索引不變）
重復(fù)上述過程，直到索引超過數(shù)組邊界。如果符合1，退出重復(fù)。這里，我們認(rèn)為本題找到目標(biāo)值即可，無需查找是否有其他位置的目標(biāo)值。

根據(jù)上述思路，通過向左下移動，達(dá)到整行或者整列的剔除，實現(xiàn)比較快速的查找。可以把這個過程理解為剝洋蔥，一層層剝開外層的非目標(biāo)層，查找內(nèi)部的目標(biāo)值。

三、Java實現(xiàn)

源程序：

package jz_offer;

public class problem03
{
    /**
     * -查找二維數(shù)據(jù)arr中是否存在數(shù)值num
     * @param   arr：二維數(shù)組
     *            num：目標(biāo)值
     * @return  在二維數(shù)組中是否找到了目標(biāo)值num，返回類型boolean
     */
    public static boolean findNum(int[][] arr,int num){
        boolean flag=false;  //標(biāo)志位，為true時表示找到目標(biāo)值
        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]

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72889.html

相關(guān)文章

  • LintCode547/548_求數(shù)組交集不同解法小結(jié)

    摘要：求數(shù)組交集不同解法小結(jié)聲明文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處求數(shù)組交集要求元素不重復(fù)，給出兩個數(shù)組，求二者交集且元素不重復(fù)，查找會超時解法一排序二分查找算法超時主要發(fā)生在大數(shù)組查找過程，因此采用二分查找提升查找效率，交集用保存實現(xiàn)去重解法 LintCode547/548_求數(shù)組交集不同解法小結(jié) [TOC] 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處：[1] https://segme...

    gxyz 評論0 收藏0

  • Java編程基礎(chǔ)06——數(shù)組

    摘要：空指針異常原因數(shù)組已經(jīng)不在指向堆內(nèi)存了。當(dāng)訪問數(shù)組不存在的索引時，就會出現(xiàn)數(shù)組索引越界異常數(shù)組的操作遍歷掌握案例演示數(shù)組遍歷就是依次輸出數(shù)組中的每一個元素。內(nèi)循環(huán)控制的是一維數(shù)組的長度。 1.數(shù)組概述和定義格式說明 A:為什么要有數(shù)組(容器)： 為了存儲同種數(shù)據(jù)類型的多個值 B:數(shù)組概念： 數(shù)組是存儲同一種數(shù)據(jù)類型多個元素的集合。也可以看成是一個容器；數(shù)組既可以存儲基本數(shù)據(jù)類型，也可...

    荊兆峰 評論0 收藏0

  • 【刷算法】二維數(shù)組中的查找

    摘要：題目描述在一個二維數(shù)組中每個一維數(shù)組的長度相同，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。分析例如二維數(shù)組，，如果按照常規(guī)的查找，從開始，那么，和都大于，接下來該怎么辦呢這就陷入了一個無法進(jìn)行下去的局面。 題目描述 在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的...

    Worktile 評論0 收藏0

  • java知識體系梳理-->數(shù)組

    摘要：知識體系梳理流程圖一維數(shù)組數(shù)組概述數(shù)組是指一組數(shù)據(jù)的集合，數(shù)組中的每個數(shù)據(jù)被稱作元素。定義打印數(shù)組元素方法按照給定的格式打印題目分析通過觀察發(fā)現(xiàn)，要實現(xiàn)按照指定格式，打印數(shù)組元素操作。按照這種方式，數(shù)組循環(huán)多圈以后，就完成了數(shù)組元素的排序。 知識體系梳理流程圖 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一維數(shù)組 ...

    james 評論0 收藏0

  • 【LC總結(jié)】Iterator題目<Zigzag 1&2><BST>&

    摘要：方法直接查找數(shù)組的位的迭代器，調(diào)用方法得到的整數(shù)即為要返回的元素。再寫迭代器的方法返回指針元素的并讓指針通過遞歸方法指向下一個元素。 Zigzag Iterator Problem Given two 1d vectors, implement an iterator to return their elements alternately. Example Given two 1d ...

    WelliJhon 評論0 收藏0

發(fā)表評論

0條評論

王晗

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<