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

2024-02-28 22:20

本文主要是介绍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)错误的集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/756795

相关文章

科研绘图系列:R语言扩展物种堆积图(Extended Stacked Barplot)

介绍 R语言的扩展物种堆积图是一种数据可视化工具,它不仅展示了物种的堆积结果,还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异,为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

如何确定 Go 语言中 HTTP 连接池的最佳参数?

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式: 一、分析应用场景和需求 并发请求量: 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高,需要设置较大的连接池参数以满足需求。例如,对于一个高并发的 Web 服务,可能同时有数百个请求在处理,此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景,观察系统在不同并发请求下的性能表现,从而

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员,我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书,我不敢乱推荐,尤其是国内作者写的书,往往七拼八凑,漏洞百出。 但是,李忠老师的《C语言非常道》值得一读。对了,李老师有个官网,网址是: 李忠老师官网 最棒的是,有配套的教学视频,可以试看。 试看点这里 接下来言归正传,讲解指针。以下内容很多都参考了李忠老师的《C语言非

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou