首页 > 代码库 > 剑指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 数组所有数字出现两次,只有两个出现了一次,找出这两个数字