首页 > 其他 > 详细

260. Single Number III

时间:2016-05-15 21:21:34      阅读:145      评论:0      收藏:0      [点我收藏+]

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

The order of the result is not important. So in the above example, [5, 3] is also correct.

Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

 

 1 /**
 2  * Return an array of size *returnSize.
 3  * Note: The returned array must be malloced, assume caller calls free().
 4  */
 5 int* singleNumber(int* nums, int numsSize, int* returnSize) {
 6     int flag = 0;
 7     int i;
 8     int k = 1;
 9     int *res;
10     res = (int*)malloc(2 * sizeof(int));              //必须malloc 不然通不过
11     res[0] = res[1] = 0;
12     for(i = 0; i < numsSize; i++)                        //先异或出这2个数
13         flag ^= nums[i];
14     while(1)
15     { 
16         if(k & flag)                               //  找出二进制中第一个为1的位,那么这2个数这个位,其中一个为1,另外一个为0
17             break; 
18         k = k << 1;
19     }
20     for(i = 0; i < numsSize; i++)
21     {
22         if(k & nums[i])                              //把所有这位为1的归位一类,
23             res[0] ^= nums[i];                         //异或出这位为0的数
24         else                                               //同理异或处这位位1的数
25             res[1] ^= nums[i];
26         
27     }
28     *returnSize = 2;
29     return res;
30 }

 

260. Single Number III

原文:http://www.cnblogs.com/boluo007/p/5496012.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!