Problem 3：二維數組中的查找

王晗發布于2019-08-16 14:16 / 463人閱讀

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

一、題目描述

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

二、思路分析

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

而右上側和左下側點都可能有大于該點的點，初步可認為，大于該值的點位于右側和下側。
因此，我們可以根據該數組的特點進行逐行剔除，達到縮小范圍，查找目標值的目的。

算法思路

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

選擇右上角為初始點，執行下述操作
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]

GPU云服務器云服務器 javascript中的二維數組 java中的二維數組 python中的二維數組找出一個二維數組中的鞍點

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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