1、 在一个排序的二维数组中,查找某个整数

简介: 在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

题目描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

解法一:

使用二分法查找实现

class Solution 
{
    public:
    bool Find(int target, vector<vector<int> > array) {
        for(int i=0;i<array.size();i++)
        {
            int low=0;
            int high=array[i].size()-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;
    }
};

运行时间;10ms 1500k

解法二

利用二维数组由上到下,由左到右递增的规律,选取右上角或者左下角的元素a[row][col]与target进行比较,

当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,即col--;

当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,即row++;

以下选择的是右上角的实现:

class Solution {
    public:
    bool Find(int target, vector<vector<int>> array) {
        int row=0;
        int col=array[0].size()-1;
        while(row<=array.size()-1&&col>=0){
            if(target==array[row][col])
                return true;
            else if(target>array[row][col])
                row++;
            else
                col--;
        }
        return false;
    }
};

运算时间 13ms 1508k

heda3
+关注
目录
打赏
0
0
0
0
5
分享
相关文章
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
arr = [1,2,5,8,9,10,20,30,40] 有一个从小到大排序好的数组,现在输入一个数,要求按照原来的规律插入到数组中
arr = [1,2,5,8,9,10,20,30,40] 有一个从小到大排序好的数组,现在输入一个数,要求按照原来的规律插入到数组中
123 0
|
3月前
|
巧用二维数组进行编号排序以及创建新数组排序编号和一个杨辉三角的实现
巧用二维数组进行编号排序以及创建新数组排序编号和一个杨辉三角的实现
82 1
|
8月前
44.从键盘输入12个数存入二维数组a[3][4]中,编写程序求出最大元素的值及它所在的行号和列号
44.从键盘输入12个数存入二维数组a[3][4]中,编写程序求出最大元素的值及它所在的行号和列号
112 0
|
8月前
根据二维数组中的某个字段进行排序
根据二维数组中的某个字段进行排序
36 0
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
98 0
wustojc4002三个整数排序
wustojc4002三个整数排序
46 0
三整数排序
题目描述 从键盘输入三个整数x,y和z,按从大到小的顺序输出它们的值。
74 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等