衡水企业网站制作,房屋装修全包清单,网站做多少层级,wordpress 协同数组中只出现一次的两个数字 题目描述数据范围提示 示例示例1示例2 题解解题思路位运算方法步骤#xff1a; 代码实现代码解析时间与空间复杂度按位与操作获取最小位1的原理为什么选择最低有效的 1 位而不是其他位#xff1f; 题目描述
一个整型数组里除了两个数字只出现一次… 数组中只出现一次的两个数字 题目描述数据范围提示 示例示例1示例2 题解解题思路位运算方法步骤 代码实现代码解析时间与空间复杂度按位与操作获取最小位1的原理为什么选择最低有效的 1 位而不是其他位 题目描述
一个整型数组里除了两个数字只出现一次其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围
数组长度2 ≤ n ≤ 1000数组元素值0 val ≤ 1000000
要求
时间复杂度O(n)空间复杂度O(1)
提示
输出时按非降序排列。
示例
示例1
输入
[1,4,1,6]返回值
[4,6]说明
返回的结果中较小的数排在前面。
示例2
输入
[1,2,3,3,2,9]返回值
[1,9]题解
解题思路
本题要求找出数组中出现一次的两个数字。由于数组中只有两个数字出现一次其他数字都出现了两次。我们可以利用 位运算 来高效求解。
位运算方法 异或运算我们可以利用异或^的特性来解决这个问题。异或运算有以下特点 a ^ a 0即相同的数字异或结果为0a ^ 0 a即任何数字与0异或结果为其本身异或运算具有交换律和结合律。 求解步骤 将数组中的所有数字进行异或。由于其他数字都出现了两次它们的异或结果为0最后剩下的就是两个只出现一次的数字的异或结果。假设这两个只出现一次的数字为 x 和 y那么 x ^ y 就是一个非0的值。我们可以根据 x ^ y 的二进制表示找到 x 和 y 的不同位。通过分组操作将所有数字根据该位进行分组这样就可以分别找到 x 和 y。
步骤
对数组中的所有元素进行异或得到 xor。找到 xor 中某一位的为1的位置即 xor 中第一个为1的位置这表示 x 和 y 在这一位上不同。根据该位置将所有数字分为两组分别对每组中的数字异或得到的结果即为 x 和 y。
代码实现
/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param nums int整型一维数组* param numsLen int nums数组长度* return int整型一维数组* return int* returnSize 返回数组行数*/
int* FindNumsAppearOnce(int* nums, int numsLen, int* returnSize ) {*returnSize 2;int* result (int*)malloc(*returnSize * sizeof(int));int xor 0;for (int i 0; i numsLen; i) {xor ^ nums[i];}int right1 xor (-xor);*result 0; // 初始化结果数组*(result 1) 0;for (int i 0; i numsLen; i) {if ((nums[i]right1) !0)*result ^ nums[i];else*(result 1) ^ nums[i];}if(*(result 1)*result){*(result 1)^*result;*result^*(result 1);*(result 1)^*result;}return result;// write code here
}代码解析 第一步我们通过对所有数字进行异或得到 xorResult这个值是两个只出现一次的数字的异或结果。 第二步我们找到 xorResult 中最低为1的位。通过 xorResult (-xorResult) 操作即xorResult (~xorResult1) 我们获取到这一位的值。 第三步根据该位的值将数组中的元素分为两组 如果该位为1则将元素分配到一组在 num1 中异或如果该位为0则将元素分配到另一组在 num2 中异或。 第四步异或操作后num1 和 num2 就分别是我们要找的两个只出现一次的数字。 返回结果最后我们返回按非降序排列的两个数字。
时间与空间复杂度
时间复杂度O(n)我们遍历了一遍数组进行异或运算。空间复杂度O(1)我们只用了常数空间来存储临时变量。 要理解为什么 xorResult (-xorResult)或者等价的 xorResult (~xorResult 1)) 能得到 xorResult 中最低有效的 1 位的值我们需要从二进制和补码的角度来分析。
按位与操作获取最小位1的原理
xorResult (-xorResult) 的效果依赖于补码的特性。我们逐步解析这个过程
xorResult 中最低有效的 1 位前的所有位都是 0 或者 1而这个最低有效的 1 位后的所有位都应该是 0。-xorResult 是 xorResult 取反再加 1 的结果它和 xorResult 在最低有效 1 位之前的二进制位完全相反且在最低有效 1 位后面与 xorResult 的二进制位相同。
让我们举一个具体的例子假设 xorResult 12其二进制表示为 x o r R e s u l t 00000000000000000000000000001100 xorResult 00000000 00000000 00000000 00001100 xorResult00000000000000000000000000001100
-xorResult即 ~xorResult 1为 − x o r R e s u l t 11111111111111111111111111110100 -xorResult 11111111 11111111 11111111 11110100 −xorResult11111111111111111111111111110100
然后进行按位与操作 x o r R e s u l t ( − x o r R e s u l t ) 00000000000000000000000000001100 11111111111111111111111111110100 00000000000000000000000000000100 xorResult \ (-xorResult) 00000000 00000000 00000000 00001100 \ 11111111 11111111 11111111 11110100 00000000 00000000 00000000 00000100 xorResult(−xorResult)000000000000000000000000000011001111111111111111111111111111010000000000000000000000000000000100
得到的结果是 00000000000000000000000000000100 00000000 00000000 00000000 00000100 00000000000000000000000000000100
这个结果是 4也就是最低有效 1 位的值。
为什么选择最低有效的 1 位而不是其他位
最后得到的xor是所有的异或位a^b,如果最低为为1说名最低有效的 1 位是因为它是异或结果中最早出现的差异位它能够最早地分割数组使得我们能更快地定位到这两个不同的数字。分割成两组一组为这位是1和多个出现两次的数然后一组为这位是0和多个出现两次的数多个出现两次的数异或后为0。所以解决
