首页 > 编程语言 >每日算法之二维数组中的查找

每日算法之二维数组中的查找

时间:2022-11-25 09:57:50浏览次数:44  
标签:return target int 算法 二维 查找 数组 length array

JZ4二维数组中的查找

描述

在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]]
给定 target = 7,返回 true。
给定 target = 3,返回 false。
 
进阶:空间复杂度 O(1)O(1) ,时间复杂度 O(n+m)O(n+m)

思路

利用该二维数组的性质:

每一行都按照从左到右递增的顺序排序,
每一列都按照从上到下递增的顺序排序
改变个说法,即对于左下角的值 m,m 是该行最小的数,是该列最大的数
每次将 m 和目标值 target 比较:

当 m < target,由于 m 已经是该行最大的元素,想要更大只有从列考虑,取值右移一位
当 m > target,由于 m 已经是该列最小的元素,想要更小只有从行考虑,取值上移一位
当 m = target,找到该值,返回 true
用某行最小或某列最大与 target 比较,每次可剔除一整行或一整列

代码

package mid.JZ4二维数组中的查找;

public class Solution {
    public boolean Find(int target, int [][] array) {
        //先判断特殊情况
        if (array.length == 0) return false;
        int n = array.length;
        if (array[0].length == 0) return false;
        int m = array[0].length;

        //从上下最大,左右最小开始遍历
        for (int i = n -1, j = 0; i >= 0 && j < m;) {
            //如果大了
            if (array[i][j] > target) {
                //往上走
                i--;
            } else if(array[i][j] < target) {
                //小了 往右走
                j++;
            } else {
                //如果等于,返回true
                return true;
            }
        }
        return false;

    }
}

标签:return,target,int,算法,二维,查找,数组,length,array
From: https://www.cnblogs.com/loongnuts/p/16924215.html

相关文章

  • js二维数组行列互换
    constaa=[[1,2,3],[4,5,6],[7,8,9]]functiontransfer(aa){constnewArr=aa[0].map((col,i)=>{returnaa.map(row=>{return......
  • 算法5: LeetCode_单链表_两数相加
    题目:*给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照逆序的方式存储的,并且每个节点只能存储一位数字。*请你将两个数相加,并以相同形式返回一个......
  • 算法基础
    算法——差分https://www.acwing.com/problem/content/description/799/#include<bits/stdc++.h>usingnamespacestd;constintN=100010;inta[N],b[N];intm......
  • DBSCAN聚类算法
    1.基于密度的聚类算法基于密度的聚类算法主要思想是只要邻近区域的密度(对象的个数)超过某个阈值,就把它加入到与之相近的聚类中。基于密度的聚类算法代表有DBSCAN算法......
  • 排序算法
    零、总览(一)术语说明稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;内排序:所有排序操作都在内存中完成......
  • 【算法】一些有用的知识
    前言本篇文章收录那些一般不会考裸题,但是常用于算法优化等处的算法们。预计会有以下几种板块:数学字符串其他一、数学1.快速幂快速幂intqpow(intx,inty){ i......
  • 优维科技CTO访谈实录:“大场景+小算法”构建AiOps运维技术哲学
    智能运维、自动化运维发展到现在,已经有将近7成的IT管理者学会利用大数据、人工智能产品及解决方案赋能团队,在生产效率、适应性和决策能力等层面实现了切实有效的正向转型。......
  • 一维数组的排序算法
    一维数组的排序算法冒泡排序气泡在水中向上涌数据在数组中不断的向前移动冒泡排序的过程代码运行publicclassarry7{publicstaticvoidmain(String[]args){......
  • java基础——二维数组基本概念
    之前我们已经知道什么是数组(一维数组)java基础——数组,数组的存取 这里补充一点: 数组本身是引用数据类型,数组的元素 可以是  基本数据类型 跟 引用数据类型 ......
  • 设计师如何通过算法提升产品转化率
    小结:1、强化学习奖惩逻辑2、为了使得累加之后不会正负抵消,我们会把得出来的距离数值做一个平方,这个方法叫做最小二乘法模型:一元线性回归模型算法:最小二乘法损失函......