做一个小网站需要多少钱,专业论坛网站开发开发,chatgpt 网址,wordpress 手机 登陆个人主页#xff08;找往期文章包括但不限于本期文章中不懂的知识点#xff09;#xff1a; 我要学编程(ಥ_ಥ)-CSDN博客
题目#xff1a; 在一个整型数组中#xff0c;只有一个数字出现一次#xff0c;其他数组都是成对出现的#xff0c;请找出那个只出现一次的数字。…个人主页找往期文章包括但不限于本期文章中不懂的知识点 我要学编程(ಥ_ಥ)-CSDN博客
题目 在一个整型数组中只有一个数字出现一次其他数组都是成对出现的请找出那个只出现一次的数字。 例如 数组中有1 2 3 4 5 1 2 3 4只有5出现一次其他数字都出现2次找出5 这个题目说难也难说容易也容易主要是看能不能想到。这个题目是让我们在相同中找不同只有5是出现一次其他数字都出现2次找出5就可以想到一个操作符按位异或^同为0异为1。不过这里有一个知识点0 ^ n n n ^ n 0。这个题目在下面这篇文章中讲过可以去看看。 利用操作符解题的精彩瞬间-CSDN博客
题目 一个数组中只有两个数字是出现一次其他所有数字都出现了两次。 编写一个函数找出这两个只出现一次的数字。 例如 有数组的元素是1234512346 只有5和6只出现1次要找出5和6. 如果我们还用异或的方法就会发现这个结果不是我们想要的。但是这个思想还是用异或的方法。因为这个题目还是找不同只不过是多了一个数并且要全部输出。但是如果我们把这个数组分为两个数组每个数组中都只有一个数出现一次然后再用上面的方法异或 得出结果分别输出。我们现在就是要找到这个分组的依据如果根据这个例子我们就会发现可以用奇偶的方法把这两个不同的数个分开。
#include stdio.h
void FindNum(int* p, int sz)
{int num1 0;int num2 0;int i 0;for (i 0; i sz; i){if (*(pi) % 2 1){num1 ^ *(p i);}else{num2 ^ *(p i);}}printf(%d %d\n, num1, num2);
}int main()
{int arr[] { 1,2,3,4,5,6,4,3,2,1 };int sz sizeof(arr) / sizeof(arr[0]);FindNum(arr, sz);return 0;
} 当然这个方法有局限性只限于这两个出现一次的数一个是奇数一个是偶数。如果两个都是奇数或者偶数不行。
这里还是用异或将这个数组中的数全部异或到一起把最终的结果转化为二进制。看看二进制中的1随机选一个1作为异或的结果。画图演示
我们把倒数第二位的1作为分界限。把这个位是1的分成一组是0的分成1组。当然这里可能会有小伙伴有疑惑这个1只是把5和6分开了但是那些其它的数字呢其实这里我们的目的从一开始就是要把5和6分开就行了。因为那些数都是一对的不管是前面的奇偶性还是二进制位都是一样的我们分开了一个另外一个也会跟着走。
#include stdio.h
void FindNum(int* p, int sz)
{//第一步把全部的数异或到一起得出最终的结果int ret 0;int i 0;for (i 0; i sz; i){ret ^ *(p i);}//将ret的一个二进制位1作为分界线1是一组0是一组int num1 0;int num2 0;for (i 0; i sz; i){//ret 1就是把倒数第二位的二进制位移到倒数第一位只有这样才能判断是否为1//(*(p i))) 1 就是和上面一样的效果。if( ((ret 1) ((*(p i))) 1 ) 1){num1 ^ *(p i);}else{num2 ^ *(p i);}}printf(%d\n, num1);printf(%d\n, num2);
}int main()
{int arr[] { 1,2,3,4,5,6,4,3,2,1 };int sz sizeof(arr) / sizeof(arr[0]);FindNum(arr, sz);return 0;
}
但是这个代码也是有缺陷的只能把倒数第二位的找出就像5和6。如果要推广的话就不可以除非我们把那个异或的数的第K位为1找出来移到想要的位数来比较。得到K的值
#include stdio.h
void FindNum(int* p, int sz)
{//第一步把全部的数异或到一起得出最终的结果int ret 0;int i 0;for (i 0; i sz; i){ret ^ *(p i);}//将ret的一个二进制位1作为分界线1是一组0是一组//接下来就是找这个1。int k 0;for (i 0; i 32; i)//最坏的结果就是找32次{if (((ret i) 1) 1)//最低位为1则说明是1{k i;break;}}int num1 0;int num2 0;for (i 0; i sz; i){//i k就是把i的二进制位移了k位看看与1的结果如果是1则说明该位是1if( (((*(p i)) k) 1) 1){num1 ^ *(p i);}else{num2 ^ *(p i);}}printf(%d\n, num1);printf(%d\n, num2);
}int main()
{int arr[] { 1,2,3,4,5,6,4,3,2,1 };int sz sizeof(arr) / sizeof(arr[0]);FindNum(arr, sz);return 0;
}
这里就是可以任意找了。注意一下在判断数组元素与1的结果是否为1时要把括号加上去阐明优先运算。
