<rp id="qpc6k"><optgroup id="qpc6k"><bdo id="qpc6k"></bdo></optgroup></rp>
  • <mark id="qpc6k"><noframes id="qpc6k"><b id="qpc6k"></b></noframes></mark>
    1. <input id="qpc6k"></input>
    <u id="qpc6k"></u>

      <video id="qpc6k"><input id="qpc6k"><p id="qpc6k"></p></input></video>
      <u id="qpc6k"><dl id="qpc6k"></dl></u>
      <b id="qpc6k"><kbd id="qpc6k"></kbd></b>

      首頁 > 試題廣場 > 二維數組中的查找
      [編程題]二維數組中的查找
      在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。
      class?Solution?{
      public:
      ????bool?Find(int?target,?vector<vector<int>?>?array)?{
      ????????int?h=array.size();
      ????????int?l=array[0].size();
      ????????int?cnt=0;
      ????????for(int?i=0;i<h;i++)
      ????????{
      ????????????for(int?j=0;j<l;j++)
      ????????????{
      ????????????????if(array[i][j]==target)
      ????????????????{
      ????????????????????return?true;
      ????????????????????cnt++;
      ????????????????????break;
      ????????????????}
      ????????????}
      ????????}
      ????????if(cnt==0)
      ????????????return?false;
      ????}
      };

      發表于 2019-08-05 23:38:48 回復(0)
      更多回答
      推薦
      /* 思路
      * 矩陣是有序的
         查看全部
      編輯于 2015-06-18 16:50:07 回復(210)
      兩種思路
      一種是:
      把每一行看成有序遞增的數組,
      利用二分查找,
      通過遍歷每一行得到答案,
      時間復雜度是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 回復(53)
      從左下角元素往上查找,右邊元素是比這個元素大,上邊是的元素比這個元素小。于是,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)
      JS了解一下
      function Find(target, array)
      {
      ? ? return array.some(arr=>arr.some(e=>e===target))
      }
      發表于 2018-04-04 14:34:31 回復(13)
      最佳答案:沒有之一。思路:首先我們選擇從左下角開始搜尋,(為什么不從左上角開始搜尋,左上角向右和向下都是遞增,那么對于一個點,對于向右和向下會產生一個岔路;如果我們選擇從左下腳開始搜尋的話,如果大于就向右,如果小于就向下)。
      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)
      這個編譯器特別蛋疼。。。
      發表于 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)
      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)
      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)

      一、給出的是方陣

      [[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 回復(1)
      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)
      微拍福利