开发者社区> 奶berber> 正文

剑指Offer_4_二维数组中的查找

简介: 题目描述       在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。      例 :     1   2    8     9      2   4    9    12      4   7   10   13      6   8   11   15     在这个数组中查找数字 9 ,  则返回true 。
+关注继续查看

题目描述

      在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
     例 :     1   2    8     9
     2   4    9    12
     4   7   10   13
     6   8   11   15
    在这个数组中查找数字 9 ,  则返回true 。 查找数子5 ,则返回false 。
 
 分析 : 因为二位数组每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。
      通常的思路可能是比较对角线,但是如果要查找的数相对于当前位置可能在两个区域出现,而且有重叠,
      那就麻烦了。
 
      所以一个更简单的方法是选取数组右上角的数字(当前数),要查找的数(目标数),如果当前数大于目标数,因为列是            按从上到下递增,那么当前数所在的一列就可以排除掉了,令当前数行标减一,成为新的当前数,再去做比较。
    例:
                     查找数字7 
 
          从右上角开始,当前数是9 , 9大于7 ,那么9所在的列不可能有数7 , 此列排除 。
              行标减一后生成新的二位数组,选定新的当前数8  , 8大于7 ,同理删去此列 。

 

                            当前数2 ,小于7 , 此时列表加一,去除第一行 。

                当前数4 ,小于7 ,此时列表加一,去除第一行 。

                当前数7 , 等于7 , 返回true。

 

   下面分别列出c++和Java实现

  c++ :

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std ;
 4 
 5 int main()
 6 {
 7     int a[4][4] = {
 8                  {1,2,8,9},
 9                  {2,4,9,12},
10                  {4,7,10,13},
11                  {6,8,11,15},
12                 } ;
13     int n ;
14     cin >> n ;  // 要查找的元素
15     int i=0 ;
16     int j=3 ;
17     while((i<=3)&&(j>=0)){
18         if(a[i][j]>n){
19             j-- ;
20         }else if(a[i][j]<n){
21             i++ ;
22         }else if(a[i][j]==n){
23             cout << "yes" <<endl ;
24             break ;
25         }
26     }
27     return 0 ;
28 }

Java:

 1 import java.util.Scanner;
 2 
 3 public class Find {
 4     public static void main(String[] args) {
 5         int a[][] = {
 6                 {1, 2, 8, 9},
 7                 {2, 4, 9, 12},
 8                 {4, 7, 10, 13},
 9                 {6, 8, 11, 15},
10                      };
11         int n ;
12         Scanner cin = new Scanner(System.in) ;
13         n = cin.nextInt() ;
14         int i=0 ;
15         int j=a.length - 1;
16         while((i<=3)&&(j>=0)){
17             if(a[i][j]>n){
18                 j-- ;
19             }else if(a[i][j]<n){
20                 i++ ;
21             }else if(a[i][j]==n){
22                 System.out.println("yes");
23                 break ;
24             }
25         }
26     }
27 }

 

 

           
 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
在排序数组中查找数字I(剑指offer 53-I)
在排序数组中查找数字I(剑指offer 53-I)
15 0
数据结构与算法之美 | 二分查找:剑指offer53 在排序数组中查找数字
我们先分析如何找到第一个k。二分查找算法总是先拿数组中间的数字和k做比较。如果中间的数字比k大,那么k只有可能出现在数组的前半段,下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小,那么k只有可能出现在数组的后半段,下一轮我们只在数组的后半段查找就可以了。
10 0
LeetCode 5428. 重新排列数组
给你一个数组 nums ,数组中有 2n 个元素,按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。
12 0
「LeetCode」剑指Offer-04二维数组中的查找⚡️
「LeetCode」剑指Offer-04二维数组中的查找⚡️
38 0
「LeetCode」剑指Offer-53 I.在排序数组中查找数字 I
「LeetCode」剑指Offer-53 I.在排序数组中查找数字 I
39 0
「LeetCode」215-数组中的第K个最大元素⚡️
「LeetCode」215-数组中的第K个最大元素⚡️
50 0
【LeetCode剑指offer04】二维数组中的查找(简单数学)
从左到右,从上到下,两条路径都是数值从小到大排列,为了确定target是否存在,可以换个起点开始,如从右上角(其实从左下角开始也行),这时候就很神奇了
50 0
[解题报告]【第27题】给定一个 n 个元素的数组,再给出 x ,查找 x 在数组中的下标 | 穷举法
[解题报告]【第27题】给定一个 n 个元素的数组,再给出 x ,查找 x 在数组中的下标 | 穷举法
96 0
Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)
Leetcode34在排序数组中查找元素的第一个和最后一个位置(二分法求解)
49 0
+关注
奶berber
这辈子没法做太多事情,所以每做一件事都要做到精妙绝伦
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载