网站改版对seo影响,wordpress数据库修改,编程软件scratch下载,软件定制解决方案这里写目录标题 问题详情分析问题代码展示 问题详情
剑指 Offer 56#xff1a;
一个整型数组 nums 里除两个数字之外#xff0c;其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)#xff0c;空间复杂度是O(1)。
示例#xff1a; 输入
一个整型数组 nums 里除两个数字之外其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)空间复杂度是O(1)。
示例 输入nums [4,1,4,6] 输出[1,6] 或 [6,1] 分析问题
首先我们知道两个相同的数异或结果是0而0异或任何数都是不变的而且异或运算是支持交换律和结合律 C语言中的异或符号是’^’ 如3533350^55; 那如果数组nums中只有一个数出现一次其它的数都出现了两次那我们将所有的数组元素进行异或运算不就可以得出结果了吗
但是在这里有两个只出现一次的数字我们该怎么办呢如果我们也将其所有的数组元素都异或在一起那得出的数是不是就是那两个出现一次的数字异或的结果 例[1,1,2,3,4,4,5,5] 2 0010;3 0011 所以1123445^5 023 0001 1 那我们能不能将这两个数分开来呢使这两个单独出现的数在它们所在的数组都是单独存在的。再分别异或就能得出这两个数。
那如何分出这两个数呢
我们先把数组nums中所有元素异或起来。 1123445^5 023 0011^0010 0001 相同的数异或为00与非0数异或为非0数本身。 所以全部异或在一起就等价于两个单独数异或.
异或得出值0001设这个值为ret 。通过观察可以发现ret为1的位就说明两个单独数的相同位是不同的。要么是1要么是0。不可能重复。
那我们如何去找到为1的位
我们定义一个变量m 1将100000000000000000000000000000001不断地左移m位与ret进行运算如果结果为非0那此时1对应的位就是1向左移m位对应1的位置 回到刚刚的数组通过这个为1的位和原数组中所有元素进行运算就可以把两个单独出现的数分开。其他出现两次的数因为二进制值相同也会共同出现在同一边。 到这我们写出这个程序就不难了。
代码展示
int* singleNumbers(int* nums, size_t numsSize, int* returnSize) {int ret 0;int i 0;//保存单独出现的数异或在一起的值for (i 0; i numsSize; i){ret ^ nums[i];}int m 0;//从低向高位找到ret中第m位为1的位置, 为1代表异或在一起的两个数不相同。//while (m 32){if (ret (1 m)){break;}else{m;}}int x 0;//记录单独出现的数int y 0;//记录单独出现的数for (i 0; i numsSize; i){if (nums[i] (1 m)) //为1的为一组 直接全部异或到一起记录其值{x ^ nums[i];}else //为0的为一组{y ^ nums[i];}}int* retArr malloc(2 * sizeof(int));retArr[0] x;retArr[1] y;*returnSize 2;return retArr;
}int main()
{int p 0;int arr[] { 1,2,55,55,66,66 };int* a singleNumbers(arr, sizeof(arr) / sizeof(int), p);printf(%d , a[0]);printf(%d , a[1]);free(a);a NULL;printf(%d , p);return 0;
}
