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

C语言练习:(力扣645)错误的集合

题目链接:645. 错误的集合 - 力扣(LeetCode)

集合 s 包含从 1n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复
给定一个数组 nums 代表了集合 S 发生错误后的结果。
请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

思路解析:

本题可以考虑两个思路:

  • 数学方法

先对数组进行由小到大排序,因为缺失的数值介于前一个数值和后一个数值中间,并且在不缺失的情况下相邻两个数值差值为1,如果有数值重复,那么重复的数值和下一个不同的数值之间的差值为2,所以需要记录前一个数值存储在变量prev

📌

注意prev初始化为0,因为存在数组中缺失的数值为1,而如果数组中只有两个元素,那么最大值为2,此时在数组中找不到一个数值使得重复的数值和下一个的不同两个数值差值为2

先找到重复的数值,即下一个元素和当前元素cur相同时,存储当前数值cur到新数组的第一个元素的位置,更新prev为当前的重复数值

再继续循环,若当前数值与prev中存的数值差值大于1,说明此时已经找完了重复元素,因为不缺失数值时相邻两个数值差值为1,而此时prev中的数值和当前数值差值大于1,说明prev中的数值+1即为缺失的数值,将prev + 1存储新数组的第二个位置后更新prev

当走完该循环时,还需要注意一个问题:如果缺失的数值是数组的最大值(例如122,缺失3),此时需要单独判断,因为不存在一个数值使得后一个元素和当前元素差值为2,所以当数组的最后一个元素不等于数组的大小时,此时即为缺失数组最大值

  • 异或运算

本题同样可以考虑异或运算对重复数值和缺失数值分堆来求解,但是直接在原数组中对元素进行异或不可取

考虑到以下规律:

在原数组中,观察到重复的数值和缺失的数值都出现偶数次,而其他数值均出现奇数次,如果构造一个1~n的不缺数的数组和原数组组合,那么重复的数值和缺失的数值都出现奇数次,而其他数值均出现偶数次,在异或运算中,相同的两个数异或可以得到a^a = 0,而a^0 = a,故此时对构造的数组和原数组进行整体异或可以得到重复的数值和缺失的数值异或的结果值

故采用先构造一个数组和原数组进行整体异或,得到一个返回值ret即为重复数值和缺失数值的异或结果,因为异或运算的本质是找出两个操作数二进制位不同的位置,所以计算结果的二进制位为1的位置即为重复的数值和缺失的数值相异的位置,此时可以采用循环结合右移运算符找到相异的位置(二进制位数的下标,例如1和5中倒数第三位不同),但是本次将采用返回值与返回值的负数形式相与计算得出最低的不同位,即int position = ret & (-ret);,但是注意该语句计算的不是不同的下标位置,而是具体的值,但是该值的二进制值中为1的位置为对应的两个数不同的位置

找到最低的不同位之后,通过原数组和构造的数组中的元素与不同位的数值相与运算得到结果为0和不为0的数值,将二者分堆即可分出重复的数值和缺失的数值(因为重复的数值和缺失的数值不相同,所以二者不可能在同一堆中)

最后,因为暂时不知道重复的数值和缺失的数值具体所在的位置,所以需要遍历原数组确定重复的数值存储在新数组的第一个元素的位置,缺失的数值则放置到新数组的第二个位置

参考答案:

排序+调整(数学方法)

/** @lc app=leetcode.cn id=645 lang=c** [645] 错误的集合*/// @lc code=start
/*** Note: The returned array must be malloced, assume caller calls free().*/int cmp(const void *p1, const void *p2)
{return (*(int *)p1 - *(int *)p2);
}
int *findErrorNums(int *nums, int numsSize, int *returnSize)
{// 对已知数组进行从小到大排序qsort(nums, numsSize, sizeof(int), cmp);int *p = (int *)malloc(sizeof(int) * 2);// 定义变量记录数组中上一个元素的位置,便于计算缺失的数值int prev = 0;// 遍历数组// 1.如果找出的元素与prev中的值差值大于1,说明当前缺失的元素即为prev当前值的后一位数值// 2.如果找出的元素与prev中的值相等,说明遇到了相同元素for (int i = 0; i < numsSize; i++){int cur = nums[i]; // 遍历数组if (cur == prev){// 如果相同则表示遇到相同元素p[0] = cur; // 记录相同元素}else if (cur - prev > 1){// 如果不同且满足二者差值大于1时,则表示中间有缺失元素,并且缺失元素即为prev当前大小+1p[1] = prev + 1;}prev = cur; // 更新prev}// 存在一种情况:数组中最后一个数值小于数组长度if (nums[numsSize - 1] != numsSize){// 数组中缺失的数值为数组的最大值p[1] = numsSize;}*returnSize = 2;return p;
}
// @lc code=end

异或运算

/** @lc app=leetcode.cn id=645 lang=c** [645] 错误的集合*/// @lc code=start
/*** Note: The returned array must be malloced, assume caller calls free().*/int *findErrorNums(int *nums, int numsSize, int *returnSize)
{int *p = (int *)malloc(sizeof(int) * 2);int ret = 0;// 构造一个1-n的不缺数值的数组与原来的数组进行整体异或for (int i = 1; i <= numsSize; i++){// 将不缺数的数组进行整体异或ret ^= i;// 将缺数的数组与不缺数的数组进行整体异或ret ^= nums[i - 1];}// 当前ret中存储的值为重复数值和缺失数值异或的结果// 找出重复数值和缺失数值二者最低的不同位// 可以代替原来的移位找最低不同位算法int position = ret & (-ret);// 定义两个数值分别存储重复数值和缺失的数值int num1 = 0;int num2 = 0;// 根据最低的不同二进制位对原数组进行分组for (int i = 0; i < numsSize; i++){if ((nums[i] & position) == 0){num1 ^= nums[i];}else{num2 ^= nums[i];}}// 根据最低的不同二进制位对构造数组进行分组for (int i = 1; i <= numsSize; i++){if ((i & position) == 0){num1 ^= i;}else{num2 ^= i;}}// 因为当前不确定重复的数值和缺失的数值在num1和还是num2,所以需要与原数组进行再一次的比较找出重复数值,剩下的就是缺失的数值*returnSize = 2;for (int i = 0; i < numsSize; i++){if (nums[i] == num1){p[0] = num1;p[1] = num2;return p;}}// 如果已经确定则直接返回p[0] = num2;p[1] = num1;return p;
}
// @lc code=end

相关文章:

C语言练习:(力扣645)错误的集合

题目链接&#xff1a;645. 错误的集合 - 力扣&#xff08;LeetCode&#xff09; 集合 s 包含从 1 到 n 的整数。不幸的是&#xff0c;因为数据错误&#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值&#xff0c;导致集合 丢失了一个数字 并且 有一个数字…...

广和通发布基于MediaTek T300平台的RedCap模组FM330系列及解决方案

世界移动通信大会MWC 2024期间&#xff0c;广和通发布基于MediaTek T300平台的RedCap模组FM330系列&#xff0c;加速5G-A繁荣发展。FM330系列及其解决方案采用全球先进RedCap方案&#xff0c;满足移动宽带和工业互联对高能效的需求。 广和通FM330系列采用全球首款6nm制程且集成…...

代码随想录训练营第六十三天打卡|503.下一个更大元素II 42. 接雨水

503.下一个更大元素II 1.暴力法&#xff0c;和每日温度那一题如出一辙&#xff0c;循环数组用了一个取模运算就解决了。 class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {int n nums.size();vector<int> result;for (i…...

【web】nginx+php环境搭建-关键点(简版)

一、nginx和php常用命令 命令功能Nginxphp-fpm启动systemctl start nginxsystemctl start php-fpm停止systemctl stop nginxsystemctl stop php-fpm重启systemctl restart nginxsystemctl restart php-fpm查看启动状态systemctl status nginxsystemctl status php-fpm开机自启…...

1、什么是ETF?

ETF是Exchange Traded Fund的英文缩写&#xff0c;中文称为“交易型开放式指数基金”&#xff0c;又称“指数股”。ETF是一种指数投资工具&#xff0c;通过复制标的指数来构建跟踪指数变化的组合证券&#xff0c;使得投资者通过买卖一种产品就实现了一揽子证券的交易。简单来说…...

备战蓝桥杯Day18 - 双链表

一、每日一题 蓝桥杯真题之工作时长 这个题写代码做的话很麻烦&#xff0c;而且我也不一定能写出来&#xff0c;所以我直接就是用的excel来计算的时间和。 使用excel的做法 1.先把文件中的时间复制到excel中。 2.把日期和时间分到两列。 分成两列的步骤&#xff1a; 选中要…...

【大数据】Flink 内存管理(二):JobManager 内存分配(含实际计算案例)

《Flink 内存管理》系列&#xff08;已完结&#xff09;&#xff0c;共包含以下 4 篇文章&#xff1a; Flink 内存管理&#xff08;一&#xff09;&#xff1a;设置 Flink 进程内存Flink 内存管理&#xff08;二&#xff09;&#xff1a;JobManager 内存分配&#xff08;含实际…...

(2024,Sora 逆向工程,DiT,LVM 技术综述)Sora:大视觉模型的背景、技术、局限性和机遇回顾

Sora: A Review on Background, Technology, Limitations, and Opportunities of Large Vision Models 公和众和号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 背景 2.1…...

MySQL基础(二)

文章目录 MySQL基础&#xff08;二&#xff09;1. 数据库操作-DQL1.1 介绍1.2 语法1.3 基本查询1.4 条件查询1.5 聚合函数1.6 分组查询1.7 排序查询1.8 分页查询1.9 案例1.9.1 案例一1.9.2 案例二 2. 多表设计2.1 一对多2.1.1 表设计2.1.2 外键约束 2.2 一对一2.3 多对多2.4 案…...

el-table 多选表格存在分页,编辑再次操作勾选会丢失原来选中的数据

el-table表格多选时&#xff0c;只需要添加type"selection"&#xff0c; row-key及selection-change&#xff0c;如果存在分页时需要加上reserve-selection&#xff0c;这里就不写具体的实现方法了&#xff0c;可以查看我之前的文章&#xff0c;这篇文章主要说一下存…...

备战蓝桥杯————如何判断回文链表

如何判断回文链表 题目描述 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#xff1a;…...

linux 文本编辑命令【重点】

目录 vi&vim介绍 vim安装 vim使用 查找命令 find grep 文本编辑的命令&#xff0c;主要包含两个: vi 和 vim vi&vim介绍 作用: vi命令是Linux系统提供的一个文本编辑工具&#xff0c;可以对文件内容进行编辑&#xff0c;类似于Windows中的记事本 语法: vi file…...

C#面:ref 和 out 的区别

ref 关键字&#xff1a; 在使用 ref 关键字时&#xff0c;传递的参数必须在方法调用之前进行初始化。在方法内部&#xff0c;对 ref 参数的任何修改都会影响到原始变量。ref 参数在方法内部和外部都必须具有相同的类型。 out 关键字 out 参数在方法内部必须被赋值。在使用 ou…...

php脚本输出中文在浏览器中显示乱码

问题说明 这个问题一般出现在较低版本的php中&#xff0c;原因是php和浏览器的字符解析方式不对应 &#xff0c;导致中文字符被错误解析成乱码 &#xff08;注&#xff0c;此处的php版本任意切换是依赖于小皮面板&#xff08;phpstudy&#xff09;实现的&#xff0c;感兴趣可以…...

【Unity每日一记】角色控制器Character Contorller

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;Uni…...

Kafka入门介绍一

介绍 Kafka是一个分布式系统&#xff0c;由服务器和客户端组成&#xff0c;通过高性能TCP网络协议进行通信。它可以部署在本地和云中的裸机硬件、虚拟机和容器上环境。 服务器&#xff1a;Kafka作为一个或多个服务器的群集运行&#xff0c;这些服务器可以跨越多个数据中心或云…...

leetcode 3.反转链表;

1.题目&#xff1a; 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 2.用例&#xff1a; 3.题目解析&#xff1a; &#xff08;1&#xff09;函数头&#xff1a; 要求返回结点&#xff0c;就 ListNode* reverseList(ListNode* head)&…...

【蓝桥杯】快读|min和max值的设置|小明和完美序列|​顺子日期​|星期计算|山

目录 一、输入的三种方式 1.最常见的Scanner的输入方法 2.数据多的时候常用BufferedReader快读 3.较麻烦的StreamTokenizer快读&#xff08;用的不多&#xff09; StreamTokenizer常见错误&#xff1a; 二、min和max值的设置 三、妮妮的翻转游戏 四、小明和完美序列 五…...

半小时到秒级,京东零售定时任务优化怎么做的?

导言&#xff1a; 京东零售技术团队通过真实线上案例总结了针对海量数据批处理任务的一些通用优化方法&#xff0c;除了供大家借鉴参考之外&#xff0c;也更希望通过这篇文章呼吁大家在平时开发程序时能够更加注意程序的性能和所消耗的资源&#xff0c;避免在流量突增时给系统…...

stm32——hal库学习笔记(ADC)

这里写目录标题 一、ADC简介&#xff08;了解&#xff09;1.1&#xff0c;什么是ADC&#xff1f;1.2&#xff0c;常见的ADC类型1.3&#xff0c;并联比较型工作示意图1.4&#xff0c;逐次逼近型工作示意图1.5&#xff0c;ADC的特性参数1.6&#xff0c;STM32各系列ADC的主要特性 …...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...