首页 > 代码库 > 剑指Offer36 数组所有数字出现两次,只有两个出现了一次,找出这两个数字
剑指Offer36 数组所有数字出现两次,只有两个出现了一次,找出这两个数字
1 /************************************************************************* 2 > File Name: 38_NumbersAppearOnce.cpp 3 > Author: Juntaran 4 > Mail: JuntaranMail@gmail.com 5 > Created Time: 2016年09月03日 星期六 10时50分32秒 6 ************************************************************************/ 7 8 #include <stdio.h> 9 10 // 判断数字二进制从右往左第index位是不是111 bool isBit(int num, int index)12 {13 num = num >> index;14 return (num & 1);15 }16 17 // 所有数字出现两次,只有两个出现了一次,找出这两个数字18 void FindNumsAppearOnce(int* nums, int length, int* num1, int* num2)19 {20 if (nums==NULL || length<=2)21 return;22 23 int temp = nums[0];24 // 第一遍异或25 for (int i = 1; i < length; ++i)26 temp ^= nums[i];27 28 // 从右向左寻找temp二进制第几位是129 int index = 0;30 while ((temp & 1) == 0)31 {32 temp = temp >> 1;33 ++ index;34 }35 36 37 *num1 = 0;38 *num2 = 0;39 40 // 分组异或41 for (int i = 0; i < length; ++i)42 {43 if (isBit(nums[i], index))44 *num1 ^= nums[i];45 else46 *num2 ^= nums[i];47 }48 }49 50 int main()51 {52 int nums[] = {2,4,3,6,3,2,5,5};53 int length = 8;54 int num1 = 0;55 int num2 = 0;56 FindNumsAppearOnce(nums, length, &num1, &num2);57 printf("num1 is %d\nnum2 is %d\n", num1, num2);58 return 0;59 }
剑指Offer36 数组所有数字出现两次,只有两个出现了一次,找出这两个数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。