南京外贸网站建设案例,烟台网页制作,南通公司网站模板建站,网页设计项目教程题目链接#xff1a;645. 错误的集合 - 力扣#xff08;LeetCode#xff09; 集合 s 包含从 1 到 n 的整数。不幸的是#xff0c;因为数据错误#xff0c;导致集合里面某一个数字复制了成了集合里面的另外一个数字的值#xff0c;导致集合 丢失了一个数字 并且 有一个数字… 题目链接645. 错误的集合 - 力扣LeetCode 集合 s 包含从 1 到 n 的整数。不幸的是因为数据错误导致集合里面某一个数字复制了成了集合里面的另外一个数字的值导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 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 appleetcode.cn id645 langc** [645] 错误的集合*/// lc codestart
/*** 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 codeend 异或运算 /** lc appleetcode.cn id645 langc** [645] 错误的集合*/// lc codestart
/*** 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 codeend
