1. <dd id="qfst8"><pre id="qfst8"></pre></dd>
      <nav id="qfst8"><sub id="qfst8"><noframes id="qfst8"></noframes></sub></nav>
      <tbody id="qfst8"><pre id="qfst8"></pre></tbody>

      <dd id="qfst8"><track id="qfst8"></track></dd>
        1. 首頁 > 試題廣場 > 二維數組中的查找
          [編程題]二維數組中的查找
          在一個二維數組中(每個一維數組的長度相同),每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數,輸入這樣的一個二維數組和一個整數,判斷數組中是否含有該整數。
          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)
          微拍福利