力扣hot100:240.搜索二维矩阵II(脑子)

吉大21级算法分析与设计的一道大题,由于每一行都是排好序的直接逐行二分 可以达到:O(mlogn)。但是这里追求更广的思路可以使用其他方法。

矩阵四分:

在矩阵中用中心点比较,如果target大于中心点的值,则由于升序排列,以中心点为右下角的小矩阵就不用再查找了,因为他们一定比target小。剩下三个矩形都可能比中心点大,因此在剩下三个矩阵中继续查找;如果target小于中心点,以中心点为右下角的小矩阵可能包含,并且中心点的左下方和右上方都有可能比中心点小,因此仍然需要继续查找。

        每次可以去掉矩阵中的¼,对于每一个小矩阵它们是整个矩阵的¼,分析如下:

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {tar=target;return find(matrix,0,matrix.size()-1,0,matrix[0].size()-1);}
private:bool find(vector<vector<int>>& matrix,int row_left,int row_right,int col_top,int col_bottom){if(row_left>row_right||col_top>col_bottom||col_bottom>=matrix[0].size()||row_right>=matrix.size()) return false;if(row_left==row_right&&col_top==col_bottom&&tar!=matrix[row_left][col_bottom]) return false;int mid_row=(row_left+row_right)>>1;int mid_col=(col_top+col_bottom)>>1;if(tar==matrix[mid_row][mid_col]) return true;if(tar>matrix[mid_row][mid_col])return find(matrix,mid_row+1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col+1,col_bottom)||find(matrix,mid_row+1,row_right,mid_col+1,col_bottom);else return find(matrix,row_left,mid_row,col_top,mid_col)||find(matrix,mid_row+1,row_right,col_top,mid_col)||find(matrix,row_left,mid_row,mid_col+1,col_bottom);}
private:int tar;
};

Z字形查找:

Krahets - 力扣(LeetCode):

用二叉树来看就特别清晰了。任何一个结点均满足,左儿子小于它,右儿子大于它。如果target比它大,同一行左边一定不再满足要求,如果target比它小,同一列下边一定不再满足要求。由于我们是从右上角开始的,依次进行,每一步都使得解只能在划定的范围内,因此这样做是正确的,时间复杂度为O(m+n)。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=0,n=matrix[0].size()-1;while(m<matrix.size()&&n>=0&&matrix[m][n]!=target){if(matrix[m][n]>target) --n;else ++m;}cout<<m<<' '<<n;if(m<matrix.size()&&n>=0) return true;return false;}
};

暴力解法:

防止题目做多了不会暴力了()

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(int i=0;i<matrix.size();++i)for(int &num:matrix[i])if(num==target) return true;return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/274067.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

vue学习笔记23-组件事件⭐

组件事件 在组件的模板表达式中&#xff0c;可以直接使用$emit方法触发自定义事件&#xff1b;触发自定义事件的目的是组件之间传递数据 好好好今天又碰到问题了&#xff0c;来吧来吧 测试发现其他项目都可以 正常的run ,就它不行 搜索发现新建项目并进入以后&#xff0c;用指…

C语言--- 指针运算笔试题详解

目录 题目1&#xff1a; 题目2&#xff1a; 题目3&#xff1a; 题目4&#xff1a; 题目5&#xff1a; 题目6&#xff1a; 题目7&#xff1a; 题目1&#xff1a; #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int *ptr (int *)(&a 1);print…

新书推荐|职业教育赛教一体化课程改革系列教材之spark大数据分析

由武汉唯众智创科技有限公司统一规划并参与编写的“职业教育赛教一体化课程改革系列教材”-《spark大数据分析》正式出版上线&#xff0c;(其它八本为《云计算技术与应用》《大数据技术与应用Ⅰ》《网络综合布线》《物联网.NET开发》《物联网嵌入式开发》《物联网移动应用开发》…

Cloud-Eureka服务治理-Ribbon负载均衡

构建Cloud父工程 父工程只做依赖版本管理 不引入依赖 pom.xml <packaging>pom</packaging><parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.9.RELEA…

Request和Response对象

Request和Response都是Servlet的service方法的参数&#xff0c;Request负责获取请求数据&#xff0c;而Response负责设置相应数据~ 一.Request 1.继承体系 Tomcat负责解析数据&#xff0c;因此由Tomcat来提供实现类~ 2.获取请求数据 请求行 请求头 请求体 需要注意的是只有…

day1-C++

1>提示并输入一个字符串&#xff0c;统计该字符中大写、小写字母个数、数字个数、空格个数以及其他字符个数要求使用C风格字符串完成。 代码&#xff1a; #include <iostream> #include <string.h> using namespace std;int main() {string str ;int low 0, …

selenium高级应用

常见控件应用 复杂的控件操作1.操作Ajax选项2.滑动滑块操作 WebDriver的特殊操作元素class值包含空格property、attribute、text的区别定位动态id 截图功能页面截图页面截图&#xff0c;返回截图的二进制数据页面截图&#xff0c;返回base64的字符串截取指定元素。先定位元素&a…

【CSP试题回顾】201912-2-回收站选址

CSP-201912-2-回收站选址 关键点&#xff1a;时间复杂度 1.暴力枚举方法&#xff1a; 暴力枚举方法会遍历二维空间中的每一个点&#xff0c;对于每一个点&#xff0c;检查它的四个直接邻居是否都是垃圾点&#xff0c;然后对于每一个满足条件的点&#xff0c;再检查它的四个对…

SpringCloud Ribbon 负载均衡服务调用

一、前言 接下来是开展一系列的 SpringCloud 的学习之旅&#xff0c;从传统的模块之间调用&#xff0c;一步步的升级为 SpringCloud 模块之间的调用&#xff0c;此篇文章为第三篇&#xff0c;即介绍 Ribbon 负载均衡服务调用 二、概述 2.1 Ribbon 是什么 Spring Cloud Ribbon…

计算机网络—以太网接口和链路配置

目录 1.拓扑图 2.以太网交换机基础配置 3.配置手动模式的链路聚合 4.配置静态 LACP 模式的链路聚合 5.配置文件 1.拓扑图 2.以太网交换机基础配置 华为交换机接口默认开启了自协商功能&#xff0c;需要手动配置S1与 S2上G0/0/9和G0/0/10接口的速率。 首先修改交换机的设…

某准网招聘接口逆向之WebPack扣取

​​​​​逆向网址 aHR0cHM6Ly93d3cua2Fuemh1bi5jb20v 逆向链接 aHR0cHM6Ly93d3cua2Fuemh1bi5jb20vc2VhcmNoP3BhZ2VOdW09MSZxdWVyeT1weXRob24mdHlwZT01 逆向接口 aHR0cHM6Ly93d3cua2Fuemh1bi5jb20vYXBpX3RvL3NlYXJjaC9qb2IuanNvbg 逆向过程 请求方式&#xff1a;GET 参数构成…

分享个好用的GPT网站

目录 一、背景 二、功能描述 1、写代码 2、联网查询 3、AI绘图 一、背景 我现在的开发工作都依靠ChatGPT&#xff0c;效率提升了好几倍。这样一来&#xff0c;我有更多时间来摸鱼&#xff0c;真是嘎嘎香~ ⭐⭐⭐点击直达 ⭐⭐⭐ 二、功能描述 1、写代码 import java.ut…

C++程序设计-练手题集合【期末复习|考研复习】

前言 总结整理不易&#xff0c;希望大家点赞收藏。 给大家整理了一下C程序设计中的练手题&#xff0c;以供大家期末复习和考研复习的时候使用。 C程序设计系列文章传送门&#xff1a; 第一章 面向对象基础 第四/五章 函数和类和对象 第六/七/八章 运算符重载/包含与继承/虚函数…

力扣每日一题 将标题首字母大写 模拟 String API

Problem: 2129. 将标题首字母大写 文章目录 思路复杂度Code 思路 &#x1f468;‍&#x1f3eb; 灵神题解 复杂度 ⏰ 时间复杂度: O ( n ) O(n) O(n) &#x1f30e; 空间复杂度: O ( n ) O(n) O(n) Code class Solution {public String capitalizeTitle(String title)…

蓝桥杯2019年第十届省赛真题-修改数组

查重类题目&#xff0c;想到用标记数组记录是否出现过 但是最坏情况下可能会从头找到小尾巴&#xff0c;时间复杂度O(n2)&#xff0c;数据范围106显然超时 再细看下题目&#xff0c;我们重复进行了寻找是否出现过&#xff0c;干脆把每个元素出现过的次数k记录下来&#xff0c;直…

vue+elementUI用户修改密码的前端验证

用户登录后修改密码&#xff0c;密码需要一定的验证规则。旧密码后端验证是否正确&#xff1b;前端验证新密码的规范性&#xff0c;新密码规范为&#xff1a;6-16位&#xff0c;至少含数字/字母/特殊字符中的两种&#xff1b;确认密码只需要验证与新密码是否一致&#xff1b; 弹…

数据库管理-第159期 Oracle Vector DB AI-10(20240311)

数据库管理159期 2024-03-11 数据库管理-第159期 Oracle Vector DB & AI-10&#xff08;20240311&#xff09;1 其他distance函数2 实例演示使用其他函数寻找最近向量点函数变体简写语法 总结 数据库管理-第159期 Oracle Vector DB & AI-10&#xff08;20240311&#x…

Java中 常见的开源树库介绍

阅读本文之前请参阅------Java中 树的基础知识介绍 在 Java 中&#xff0c;有几种流行的开源树库&#xff0c;它们提供了丰富的树算法和高级操作&#xff0c;可以帮助开发者更高效地处理树相关的问题。以下是几种常见的 Java 树库及其特点和区别&#xff1a; JTree 特点…

CSS3的一些常用语句以及解释

margin和padding position static 该关键字指定元素使用正常的布局行为&#xff0c;即元素在文档常规流中当前的布局位置。此时 top, right, bottom, left 和 z-index 属性无效。 relative 该关键字下&#xff0c;元素先放置在未添加定位时的位置&#xff0c;再在不改变页面…

iconfont 字体应用

1、登录 打开阿里图标 https://www.iconfont.cn/ 2、选择心仪的图标制作 iconfont 字体。 3、图标全部选择入库之后&#xff0c; 点右上角的购物车。 添加到项目&#xff0c;是方便管理图标字体的。 也可以直接下载代码的 4、下载到本地之后&#xff0c;把里面的 iconfont.…