一个数组中所有的数都是成对出现的只有一个或者两个数

作者:湖北诺贝特科技有限公司  来源:www.nbt158.com未知  发布时间:2017-09-02 11:54:51
一个数组中所有的数都是成对出现的只有一个或者两个数字是单独的,求这个数 如果只有一个数,那么我们可以用按位亦或(^)来得到,代码如下:

#include<stdio.h> int main() { int arr[] = { 1, 1, 2, 2, 3, 3, 4 }; int size = sizeof(arr) / sizeof(int); int num = 0; for (int i = 0; i < size; i++) { num ^= arr[i]; } printf("%d\n", num); system("pause"); return 0; }

如果是两个数,那么我们可以对这个数组进行拆分,然后分别与0亦或,其拆分思想就是把数组所有的数全部亦或,所得到的的结果其本质就是那两个单独出现的数的亦或结果,由于亦或其本质就是相同为0,相异为1,所以这个数每个为1的位就是其不同的位,我们可以找出它第一个为1的位进行标记,把为一的亦或的一起,为0的亦或到一起,所得的结果就是两个数,实现代码如下:

#include<stdio.h> void find_num(int *arr, int size)//其实现功能进行函数封装,因为是要返回两个值,C语言 //实现故吧这两个值打印出来 { int num1 = 0; int num2 = 0; int end_num = 0; int flag = 0; for (int i = 0; i < size; i++) { end_num ^= *(arr + i); } while (!(end_num & 1)) { flag++; end_num >>= 1; } for (int i = 0; i < size; i++) { int tmp = arr[i] >> flag; if (tmp & 1) { num1 ^= arr[i]; } else { num2 ^= arr[i]; } } printf("num1=%d\nnum2=%d\n", num1, num2); } int main()//验证阶段 { int arr[] = { 1, 1, 2, 2, 3, 3, 4, 5 }; int size = sizeof(arr) / sizeof(arr[0]); find_num(arr,size); system("pause"); return 0; }

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:天门网站制作 http://tianmen.666rj.com


上一篇:Python 简单抓取页面学习
下一篇:最后一页