设为首页 加入收藏

TOP

260. Single Number III
2017-10-12 17:41:09 】 浏览:5230
Tags:260. Single Number III

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 }

 

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇263. Ugly Number 下一篇Single Number II

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目