• <optgroup id="100me"></optgroup>

    
    

  • <track id="100me"></track>
    首頁 > 試題廣場 > 二維數組中的查找
    [編程題]二維數組中的查找
    在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。
    推薦
    /* 思路
    * 矩陣是有序的
       查看全部
    編輯于 2015-06-18 16:50:07 回復(206)
    兩種思路
    一種是:
    把每一行看成有序遞增的數組,
    利用二分查找,
    通過遍歷每一行得到答案,
    時間復雜度是nlogn
    public class Solution {
        public boolean Find(int [][] array,int target) {
            
            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;
    
        }
    }
    
    另外一種思路是:
    利用二維數組由上到下,由左到右遞增的規律,
    那么選取右上角或者左下角的元素a[row][col]與target進行比較,
    當target小于元素a[row][col]時,那么target必定在元素a所在行的左邊,
    即col--;
    當target大于元素a[row][col]時,那么target必定在元素a所在列的下邊,
    即row++;
    public class Solution {
        public boolean Find(int [][] array,int target) {
            int row=0;
            int col=array[0].length-1;
            while(row<=array.length-1&&col>=0){
                if(target==array[row][col])
                    return true;
                else if(target>array[row][col])
                    row++;
                else
                    col--;
            }
            return false;
    
        }
    }

    編輯于 2015-12-21 22:58:19 回復(52)
    從左下角元素往上查找,右邊元素是比這個元素大,上邊是的元素比這個元素小。于是,target比這個元素小就往上找,比這個元素大就往右找。如果出了邊界,則說明二維數組中不存在target元素。

    Python版本
    # -*- coding:utf-8 -*-
    class Solution:
        # array 二維列表
        def Find(self, target, array):
            # write code here
            rows = len(array) - 1
            cols= len(array[0]) - 1
            i = rows
            j = 0
            while j<=cols and i>=0:
                if target<array[i][j]:
                    i -= 1
                elif target>array[i][j]:
                    j += 1
                else:
                    return True
            return False

    C++版本
    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            // array是二維數組,這里沒做判空操作
            int rows = array.size();
            int cols = array[0].size();
            int i=rows-1,j=0;//左下角元素坐標
            while(i>=0 && j<cols){//使其不超出數組范圍
                if(target<array[i][j])
                    i--;//查找的元素較少,往上找
                else if(target>array[i][j])
                    j++;//查找元素較大,往右找
                else
                    return true;//找到 
            }
            return false;
        }
    };

    Java版本
    public class Solution {
        public boolean Find(int target, int [][] array) {
            int rows = array.length;
            int cols = array[0].length;
            int i=rows-1,j=0;
            while(i>=0 && j<cols){
                if(target<array[i][j])
                    i--;
                else if(target>array[i][j])
                    j++;
                else
                    return true;
            }
            return false;
        }
    }

    編輯于 2017-07-20 17:04:43 回復(24)
    最佳答案:沒有之一。思路:首先我們選擇從左下角開始搜尋,(為什么不從左上角開始搜尋,左上角向右和向下都是遞增,那么對于一個點,對于向右和向下會產生一個岔路;如果我們選擇從左下腳開始搜尋的話,如果大于就向右,如果小于就向下)。
    public class Solution {
    ? ? public boolean Find(int [][] array,int target) {
    int len = array.length-1;
    ? ? ? ? int i = 0;
    ? ? ? ? while((len >= 0)&& (i < array[0].length)){
    ? ? ? ? ? ? if(array[len][i] > target){
    ? ? ? ? ? ? ? ? len--;
    ? ? ? ? ? ? }else if(array[len][i] < target){
    ? ? ? ? ? ? ? ? i++;
    ? ? ? ? ? ? }else{
    ? ? ? ? ? ? ? ? return true;
    ? ? ? ? ? ? }
    ? ? ? ? }
    ? ? ? ? return false;
    ? ? }
    }
    發表于 2015-08-26 14:14:12 回復(63)
    JS了解一下
    function Find(target, array)
    {
    ? ? return array.some(arr=>arr.some(e=>e===target))
    }
    發表于 2018-04-04 14:34:31 回復(13)
    這個編譯器特別蛋疼。。。
    發表于 2015-09-17 20:59:12 回復(18)
    class Solution {
    public:
        bool Find(vector<vector<int> > array,int target) {
           int m,n,x,y;
            m = array.size();//行數
            n = array[0].size();//列數
            x=m-1;y=0;//坐標定在左下角
            while(x>=0 && y<=n-1){
              if(target<array[x][y]){
                           x--;//遇小上移
                     }
              else if(target>array[x][y]){
                           y++;//遇大右移
                     }
              else {
                   return true;
                 }
          }
           return false; 
        }
    };
    答案正確:恭喜!您提交的程序通過了所有的測試用例
    左下角開始,遇大右移,遇小上移,直到超過邊界都沒找到,得false。否則得true。
    編輯于 2015-09-18 23:44:17 回復(17)
    public class Solution {
        public boolean Find(int [][] array,int target) {
    		int m = array.length - 1;
    		int i = 0;
    		while(m >= 0 && i < array[0].length){
    			if(array[m][i] > target)
    				m--;
    			else if(array[m][i] < target)
    				i++;
    			else 
    				return true;
    		}
            
    		return false;
        }
    }
    java 版本正確的

    發表于 2015-08-12 09:57:56 回復(11)
    function Find(target, array) {
        let lenX = array.length;
        let lenY = array[0].length;
        for (let i = lenX - 1, j = 0; i >= 0 && j < lenY;) {
            if (target > array[i][j]) {
                j++;
            }else if(target < array[i][j]) {
                i--;
            }else {
                return true
            }
        }
    }

    發表于 2017-09-11 17:18:55 回復(0)
    其實也可以從右上開始尋找;
    class Solution {
    public:
        bool Find(vector<vector<int> > array,int target) {
            int row = array.size();
    		int col = array[0].size();
    		int i,j;
    		for (i=0,j=col-1;i<row && j>=0;)
    		{
    			if (array[i][j] == target)
    			{
    				return true;
    			}
    			if (array[i][j] > target)
    			{
    				j--;
    				continue;
    			}
    			if (array[i][j] < target)
    			{
    				i++;
    			}
    		}
    		return false;
        }
    };

    發表于 2015-09-18 16:05:03 回復(0)
    # -*- coding:utf-8 -*-
    class Solution:
        # array 二維列表
        def Find(self, target, array):
            # write code here
            if not array:
                return 
            row=len(array)
            col=len(array[0])
            for i in range(row):
                for j in range(col):
                    if array[i][j]==target:
                        return True
            return False
    
    發表于 2017-09-08 22:45:58 回復(0)
    public class Solution {
        public boolean Find(int [][] array,int target) {
    	    for(int[] i : array){
                for(int j : i){
                    if(j==target)return true;
                }
            }
            return false;
        }
    }
    
    //方法簡單,代碼少
    

    發表于 2016-03-17 19:50:56 回復(19)
    <?php
    
    function Find($target, $array)
    {
        // write code here
        $rows = count($array);//行
        $columns = count($array[0]);//列
        $rs = false;
        //從右上角開始,
        for ($row = 0,$column = $columns - 1; $row < $rows && $column >= 0;) {
            if($array[$row][$column] == $target){
                $rs = true;
                break;
            }
            if ($array[$row][$column] > $target){
                //大于目標數,剔除本列
                $column--;
            }
            if($array[$row][$column] < $target) {
                $row++;
            }
        }
        return $rs;
    }
    
    發表于 2017-05-18 22:29:29 回復(3)
    測試用例不是數組在前面,要查找的數字在后面嗎,看不懂是什么意思。。
    測試用例:
    16,[[]]

    對應輸出應該為:
    false


    發表于 2015-10-01 09:46:29 回復(9)
    public class Solution {
    ? ? public boolean Find(int target, int [][] array) {
    ? ? ? ? boolean flag = false;
    ? ? ? ? int x=0;
    ? ? ? ? int y=0;
    ? ? ? ? for(int i=0;i < array.length;i++) {
    ? ? ? ? ? ? for(int j=0;j<array[i].length;j++) {
    ? ? ? ? ? ? ? ? if(target==array[i][j]){
    ? ? ? ? ? ? ? ? ? ? flag = true;
    ? ? ? ? ? ? ? ? ? ? break;
    ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? }
    ? ? ? ? }
    ? ? ? ? if(flag) {
    ? ? ? ? ? ? System.out.println("exist!"+target+",location:"+"array["+x+"]["+y+"]");
    ? ? ? ? }
    ? ? ? ? return flag;
    ? ? }
    }
    
    

    發表于 2018-07-30 20:02:01 回復(0)
    class Solution {
    public:
    	bool Find(vector<vector<int> > array, int target) {
    		int Row = array.size();
    		int Col = array[0].size();
    
    		for (int i = 0, j = Col-1; i < Row && j >=0;)
    		{
    			if (target > array[i][j])
    				i++;
    			else if (target < array[i][j])
    				j--;
    			else if (target == array[i][j])
    				return true;
    		}
    		return false;
    	}
    };
    從左下角或者右上角開始搜索均可
    

    發表于 2015-08-28 09:54:52 回復(1)

    一、給出的是方陣

    [[1,6,7,8],

    [3,7,8,9],

    [9,10,11,12],

    [12,13,14,15]]

    這種情況非常簡單,可知對角線元素應為查找元素,如果target大于對角線上某個元素,那么以此對角線為中心,左邊、上邊的元素應該都小于target

    此時只需要找到一個對角線上的點,當找個一個剛剛好大于target的元素,那么左邊和上邊進行二分查找即可,python代碼如下:
    
    
    
    # -*- coding:utf-8 -*-
    class Solution:
    ? ? # array 二維列表
    ? ? def Find(self, target, array):
    ? ? ? ? # write code here
    ? ? ? ? h, w = len(array), len(array[0])
    ? ? ? ? for i in range(min(h, w)):? ? ? # 在正方形內對角線查找
    ? ? ? ? ? ? if array[i][i] == target:
    ? ? ? ? ? ? ? ? return True
    ? ? ? ? ? ? elif (array[i][i] > target):
    ? ? ? ? ? ? ? ? for j in range(i):        # 這里可以替換成二分查找
    ? ? ? ? ? ? ? ? ? ? if (array[i][j] == target or array[j][i] == target):
    ? ? ? ? ? ? ? ? ? ? ? ? return True
                return False 

    考慮到非方陣情況例如

    [[1,6,7,8],

    [3,7,8,9],

    [9,10,11,12],

    [12,13,14,15],

    [13,14,15,16],

    [,18,21,22,23]]

    其中array的shape=(6,4)
    這時候就不能單一按照對角線考慮,應該將矩陣分塊,分成多個小方陣,利用遞歸的方式現將矩陣分塊,然后每一個小方陣按照上述對角線方式查找,python代碼如下
    # -*- coding:utf-8 -*-
    class Solution:
    ? ? # array 二維列表
    ? ? def Find(self, target, array):
    ? ? ? ? # write code here
    ? ? ? ? h, w = len(array), len(array[0])
    ? ? ? ? if (h==0 or w==0):                
                      # 遞歸退出條件,當矩陣不可再分時候,此時為行向量,順序查找或者二分查找
    ? ? ? ? ? ? for i in range(max(h,w)):
    ? ? ? ? ? ? ? ? if(target == array[i]):
    ? ? ? ? ? ? ? ? ? ? return True
    ? ? ? ? ? ? return False
        ?      # 如果按照方陣情況查找
    ? ? ? ? for i in range(min(h, w)):? ? ? # 在正方形內對角線查找
    ? ? ? ? ? ? if array[i][i] == target:
    ? ? ? ? ? ? ? ? return True
    ? ? ? ? ? ? elif (array[i][i] > target):
    ? ? ? ? ? ? ? ? for j in range(i):        # 這里可以查找二分查找
    ? ? ? ? ? ? ? ? ? ? if (array[i][j] == target or array[j][i] == target):
    ? ? ? ? ? ? ? ? ? ? ? ? return True
    ? ? ? ? if (h > w):    # 如果不是方陣,則遞歸劃分成多個小方陣查找
    ? ? ? ? ? ? return self.Find(target, [row[:w] for row in array[i+1:]])
    ? ? ? ? else:
    ? ? ? ? ? ? return self.Find(target, [row[i+1:] for row in array[:h]])
    

    編輯于 2019-03-18 15:47:07 回復(0)
    public class Solution {
    ? ? public boolean Find(int target, int [][] array) {
    ? ? ? ? if(array == null || array[0].length == 0){
    ? ? ? ? ? ? return false;
    ? ? ? ? }
    ? ? ? ? for(int i = 0;i < array.length;i++){
    ? ? ? ? ? ? int head = 0;
    ? ? ? ? ? ? int tail = array[i].length-1;
    ? ? ? ? ? ? while(head<=tail){
    ? ? ? ? ? ? ? ? int mid = (head+tail)/2;
    ? ? ? ? ? ? ? ? if(target < array[i][mid]){
    ? ? ? ? ? ? ? ? ? ? tail = mid - 1;
    ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? else if(target > array[i][mid]){
    ? ? ? ? ? ? ? ? ? ? head = mid + 1;
    ? ? ? ? ? ? ? ? }
    ? ? ? ? ? ? ? ? else
    ? ? ? ? ? ? ? ? ? ? return true;
    ? ? ? ? ? ? }
    ? ? ? ? }
    ? ? ? ? return false;? ? ? ??
    ? ? }
    }
    

    發表于 2018-07-23 08:42:55 回復(0)
    思路:
    1.如果arr數組為空,就返回false
    2.如果target小于每個數組的第一個元素,返回false
    3.target大于當前行的第一個元素,小于當前行最后一個元素,用二分查找,找不到下一行
    代碼:
    public static boolean Find(int target, int [][] arr) {
    ????????
    ????????for(int i=0;i<arr.length;i++){
    ????????????if(arr[i].length==0)
    ????????????????return false;
    ????????????int n=arr[i].length;
    ????????????if(target<arr[i][0])
    ????????????????return false;
    ????????????else if(target>=arr[i][0]&&target<=arr[i][n-1]){
    ????????????????int left=0;
    ????????????????int hight=arr[i].length-1;
    ????????????????int mid=0;
    ????????????????while(left<=hight){
    ????????????????????mid=(left+hight)/2;
    ????????????????????if(arr[i][mid]>target)
    ????????????????????????hight=mid-1;
    ????????????????????else if(arr[i][mid]<target)
    ????????????????????????left=mid+1;
    ????????????????????else
    ????????????????????????return true;
    ????????????????}
    ????????????}
    ????????}
    ????????return false;
    ????????
    ? ? }

    發表于 2017-09-24 00:18:12 回復(0)

    從右上角開始,因為左邊比它小,右邊比它大,如果當前值比target小就 行數+1,如果當前值比target小就 列數-1,最后保證不越界就好。

    class Solution {
    public:
        bool Find(int target, vector<vector<int> > array) {
            int i=0;
            int j=array[0].size()-1;
    
            while(i<array.size()&&j>=0){
                if(array[i][j]==target)
                    return true;
                if(array[i][j]<target)
                    i++;
                else if(array[i][j]>target)
                    j--;
            }
            return false;
        }
    };
    
    發表于 2017-04-14 11:23:03 回復(0)

    看了很多解法都把二維數組當做矩陣,根本沒考慮不等長的問題(好吧,按題意“每一列都按照從上到下遞增的順序排序”,應該不用考慮);
    例如以下測試案例,那些解法就過不了:
    target = 12;
    int[][] array = {{1,2,8},{2,4,9,12},{4,7},{6,8,11,15}};

    public class Solution {
    
    public boolean Find(int target, int [][] array) {
        int r=array.length-1,c=0,maxCol=0;
        for (int i=0;i<=r;i++)
            if (array[i].length>maxCol)maxCol=array[i].length;//元素最多的一行,元素數量為maxCol
        while (r>=0&&c<maxCol){
            if (c >= array[r].length)r--; //若該行元素較少,不存在第c列元素,繼續上移;
            else if (array[r][c]<target)c++;
            else if (array[r][c]>target)r--;
            else if (array[r][c]==target)return true;
        }
        return false;
        }
    }

    當然,對每一行進行二分查找或者暴力搜索不存在此問題;

    編輯于 2017-07-10 15:08:21 回復(6)
    狠狠的撸2019手机看片电影最新版