当前位置: 首页 > news >正文

从零学算法2965

2965. 找出缺失和重复的数字
给你一个下标从 0 开始的二维整数矩阵 grid,大小为 n * n ,其中的值在 [1, n2] 范围内。除了 a 出现 两次,b 缺失 之外,每个整数都 恰好出现一次 。
任务是找出重复的数字a 和缺失的数字 b 。
返回一个下标从 0 开始、长度为 2 的整数数组 ans ,其中 ans[0] 等于 a ,ans[1] 等于 b 。
示例 1:
输入:grid = [[1,3],[2,2]]
输出:[2,4]
解释:数字 2 重复,数字 4 缺失,所以答案是 [2,4] 。
示例 2:
输入:grid = [[9,1,7],[8,9,2],[3,4,6]]
输出:[9,5]
解释:数字 9 重复,数字 5 缺失,所以答案是 [9,5] 。
提示:
2 <= n == grid.length == grid[i].length <= 50
1 <= grid[i][j] <= n * n
对于所有满足1 <= x <= n * n 的 x ,恰好存在一个 x 与矩阵中的任何成员都不相等。
对于所有满足1 <= x <= n * n 的 x ,恰好存在一个 x 与矩阵中的两个成员相等。
除上述的两个之外,对于所有满足1 <= x <= n * n 的 x ,都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x

  • 最简单的,用数组统计每个数出现的次数,然后遍历数组即可
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int[] res = new int[2];int[] temp = new int[n * n + 1];for(int[] g : grid){for(int x : g){temp[x]++;}}for(int i = 1; i < temp.length; i++){if(temp[i] == 0)res[1] = i;else if(temp[i] == 2)res[0] = i;}return res;}
    
  • 数学方法:由于 a 出现两次,b 出现 0 次,所以当所有数相加时会得到 1+2+…+n + a - b,也就是说把数组中的所有数相加减去 1~n2 之和就能得到 d1 = a - b 。将所有数的平方和相加也是同理,减去 1~n2 的平方后就会剩下 d2 = a2-b2=(a+b)(a-b),最终我们可以得到 a - b = d1, a + b = d2 / d1,那么 a 和 b 就很容易计算了
  • 令 m = n2 1 − m 之和 = m ( 1 + m ) 2 { 1 - m 之和=\frac {m(1+m)} 2} 1m之和=2m(1+m)
  • 1 − m 的平方和 = m ( m + 1 ) ( 2 m + 1 ) 6 { 1 - m 的平方和=\frac {m(m+1)(2m+1)} 6} 1m的平方和=6m(m+1)(2m+1)
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int[] res = new int[2];int d1 =  -m * (1 + m) / 2;long d2 = (long) -m * (m + 1) * (2 * m + 1) / 6;for(int[] row : grid){for(int x : row){d1 += x;d2 += x * x;}}int d = (int) (d2 / d1);res[0] = (d + d1) / 2;res[1] = (d - d1) / 2;return res;}
    
  • 位运算:如果我们额外加入 1 ~ m,最终会得到一个数出现 1 次,一个数出现 3 次,其余数出现两次,而异或后出现 1 次和出现 3 次是一样,即这些数的异或和就为 a^b,那么就相当于第 260 题了,从一堆出现两次的数字中找到只出现一次的两个数字。
  • 额外计算 1 到 n2 的异或和时,可以不遍历 1 ~ n 而用 O(1) 的计算公式
    的异或和
  •   public int[] findMissingAndRepeatedValues(int[][] grid) {int n = grid.length;int m = n * n;int or = 0;for(int[] row : grid){for(int x : row){or ^= x;}}or ^= n % 2 > 0 ? 1 : m;// 计算 or 最低位的 1 后面有几个 0// 下面会根据右移 one 位来分组// 其实核心思想还是根据 or 中为 1 的某一位来分类// 所以也可以按照第 260 题的写法令 one 为 xx1x// 下面分组就能按照 x & one 是否等于 0 来分组int one = Integer.numberOfTrailingZeros(or);int[] res = new int[2];// 以下两个循环都是为了把数组中的数以及额外的 1~m 按照// 对应于 one 的那一位为 0 还是 1 分类异或进结果数组// 反正重复的数都会被异或掉,所以最终数组会剩下 a 和 bfor(int x = 1; x <= m; x++){res[(x >> one) & 1] ^= x;}for(int[] row : grid){for(int x : row){res[(x >> one) & 1] ^= x;}}// 由于我们无法区分 res 中哪个是 a 哪个是 b// 所以我们根据数组中只存在 a 没有 b 来判断// 如果数组中某个数等于 res[0] 说明 res[0] 就是 a// 那么可以直接返回for (int[] row : grid) {for (int x : row) {if (x == res[0]) {return res;}}}return new int[]{res[1], res[0]};}
    

相关文章:

从零学算法2965

2965. 找出缺失和重复的数字 给你一个下标从 0 开始的二维整数矩阵 grid&#xff0c;大小为 n * n &#xff0c;其中的值在 [1, n2] 范围内。除了 a 出现 两次&#xff0c;b 缺失 之外&#xff0c;每个整数都 恰好出现一次 。 任务是找出重复的数字a 和缺失的数字 b 。 返回一个…...

【Mac版】Java生成二维码

软件版本 IntelliJ IDEA&#xff1a;2023.2 JDK&#xff1a;17 Tomcat&#xff1a;10.1.11 Maven&#xff1a;3.9.3 技术栈 servlet谷歌的&#xff1a;zxing 生成普通的黑白二维码在二维码中间添加一个小图标 github开源项目&#xff1a;qrcode qrcode开源项目的内部是基于z…...

ROS2自定义服务接口

ROS2自定义服务接口 在src/village_interface 下构建srv文件夹 src/village_interface/srv 下新建一个BorrowMoney.srv 遵循大小写编程规范 # 客户端请求 string name uint32 money # 中间这三个横杠很重要 不能删掉 --- # 服务端响应 bool success uint32 money接口编译 修改…...

linux /www/server/cron内log文件占用空间过大,/www/server/cron是什么内容,/www/server/cron是否可以删除

linux服务器长期使用宝塔自带计划任务&#xff0c;计划任务执行记录占用服务器空间过大&#xff0c;导致服务器根目录爆满&#xff0c;需要长期排查并删除 /www/server/cron 占用空间过大问题处理 /www/server/cron是什么内容&#xff1f;/www/server/cron是否可以删除&#xf…...

C++青少年简明教程:break语句、continue语句

C青少年简明教程&#xff1a;break语句、continue语句 break语句 只能用在switch语句和循环语句&#xff08;for循环、while循环和do-while循环&#xff09;中。作用&#xff1a;跳出switch语句或提前终止循环。 break语句的基本语法如下&#xff1a; break; break语句的示例…...

MySQL实战行转列(或称为PIVOT)实战sales的表记录了不同产品在不同月份的销售情况,进行输出

有一个sales的表&#xff0c;它记录了不同产品在不同月份的销售情况&#xff1a; productJanuaryFebruaryMarchProduct AJanuary10Product AFebruary20Product BJanuary5Product BFebruary15Product CJanuary8Product CFebruary12 客户需求展示为如下的样子&#xff1a; pro…...

牛客NC164 最长上升子序列(二)【困难 贪心+二分 Java/Go/PHP/C++】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237 思路 贪心二分 所谓贪心&#xff0c;就是往死里贪&#xff0c;所以对于最大上升子序列&#xff0c;结尾元素越小&#xff0c;越有利于后面接上其他的数&#xff0c;也就可能变…...

电子烟开发【恒压、恒有效算法】

恒压算法 pwm是通过软件模拟的 pwm满值运行是250全占空比 #define D_TARGET_AVERAGE_VOLTAGE 3500 //R_ADC1_Vout &#xff1a;发热丝两端AD值 //R_ADC_FVR &#xff1a;电池电压AD值 //FVR_VOLTAGE &#xff1a;电池AD参考电压 满电值AD //R_Smk1Duty &#xff1a;最后…...

基于Open3D的点云处理22-非阻塞可视化/动态可视化

官网测试用例:examples/python/visualization/non_blocking_visualization.py 非阻塞可视化,即实时更新点云数据; 如下,动态可视化ICP的匹配过程: import open3d as o3d import numpy as npif __name__ == "__main__":o3d.utility.set_verbosity_level(o3d.ut…...

C++面试题其一

C和C的区别 C和C都是广泛使用的编程语言&#xff0c;但它们有显著的区别&#xff1a; 语言范式&#xff1a; C&#xff1a;是一种过程化编程语言&#xff0c;强调过程和函数的使用。C&#xff1a;是一种多范式编程语言&#xff0c;支持面向对象编程、泛型编程和过程化编程。 …...

CentOS7某天的samba服务搭建操作记录(还没成功)

#CentOS7 yum软件仓库阿里云 samba服务器配置失败 sensors成功了 (花了200元组装H61测试机&#xff0c;75元的主板只有一块能用&#xff0c;垃圾板但又不完全能用&#xff09; 2024.5月的某天记录如下&#xff1a; https://blog.csdn.net/dszgf5717/article/details/53732182 …...

Qt Demo:基于TCP协议的视频传输Demo

目录 1.设计思路 2.Pro文件配置 3.头文件引入 4.界面设计 5.初始化设备函数 6.发起视频链接函数 7.初始化定时器模块函数 8.TCP链接模块函数 9.处理接收的数据线程函数 10.实现功能展示 设计思路 基于TCP协议的视频传输Demo&#xff0c;设计要实现的功能主要是TCP传输还有视频&…...

内存管理【C++】

内存分布 C中的内存区域主要有以下5种 栈&#xff08;堆栈&#xff09;&#xff1a;存放非静态局部变量/函数参数/函数返回值等等&#xff0c;栈是向下增长的【地址越高越先被使用】。栈区内存的开辟和销毁由系统自动执行 堆&#xff1a;用于程序运行时动态内存分配&#xff…...

D3D 顶点格式学习

之前D3D画三角形的代码中有这一句&#xff0c; device.VertexFormat CustomVertex.TransformedColored.Format; 这是设置顶点格式&#xff1b; 画出的三角形如下&#xff0c; 顶点格式是描述一个三维模型的顶点信息的格式&#xff1b;可以包含以下内容&#xff0c; 位置…...

gmssl vs2010编译

1、虚拟机win10 x64&#xff0c;离线安装vs2010和2010sp1补丁&#xff1b; 2、安装ActivePerl_v5.28.1.0000和nasm-2.16.03-installer-x64均是默认完整安装&#xff1b; nasm官网下载&#xff1a; Index of /pub/nasm/releasebuilds/2.16.03/win64https://www.nasm.us/pub/nas…...

容器化部署gitlab、jenkins,jenkins应用示例

一、容器化部署docker和docker conpose安装 Docker&Docker-compose的安装及部署_docker 20 使用什么版本docker-compose-CSDN博客 1.docker 安装脚本 cat >01_docker.sh<<EOF #!/bin/bash yum remove docker \docker-client \docker-client-latest \docker-co…...

基于STM32的轻量级Web服务器设计

文章目录 一、前言1.1 开发背景1.2 实现的功能1.3 硬件模块组成1.4 ENC28J60网卡介绍1.5 UIP协议栈【1】目标与特点【2】核心组件【3】应用与优势 1.6 添加UIP协议栈实现创建WEB服务器步骤1.7 ENC28J60添加UIP协议栈实现创建WEB客户端1.8 ENC28J60移植UIP协议并编写服务器测试示…...

用r语言处理 Excel数据当中的缺失值方法

以下是使用 R 编程语言处理 Excel 缺失数据的一些常见方法示例代码&#xff1a;&#xff08;无需循环&#xff09; 读取包含缺失数据的 Excel 文件 data <- read.csv(“your_file.csv”) 查看数据中是否有缺失值 sum(is.na(data)) 用平均值填充缺失值 data c o l u m …...

AWS 高防和阿里云高防深度对比

随着网络攻击的不断增加&#xff0c;企业对于网络安全的需求也越来越高。在这种情况下&#xff0c;高防护服务成为了企业网络安全的重要组成部分。AWS和阿里云作为全球领先的云计算服务提供商&#xff0c;都提供了高防护服务&#xff0c;但它们之间存在着一些差异。我们九河云一…...

ctfshow web 月饼杯II

web签到 <?php //Author:H3h3QAQ include "flag.php"; highlight_file(__FILE__); error_reporting(0); if (isset($_GET["YBB"])) {if (hash("md5", $_GET["YBB"]) $_GET["YBB"]) {echo "小伙子不错嘛&#xff…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)

+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...

C# winform教程(二)----checkbox

一、作用 提供一个用户选择或者不选的状态&#xff0c;这是一个可以多选的控件。 二、属性 其实功能大差不差&#xff0c;除了特殊的几个外&#xff0c;与button基本相同&#xff0c;所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...