设为首页 加入收藏

TOP

Single Number II
2017-10-12 17:41:09 】 浏览:6331
Tags:Single Number

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

解题思路:

1.利用二进制中的位运算,有n*3个相同的数相加,那么其二进制的每一位必定是3的倍数

2.剩下的那个单独的数,就是每一位除以3的余数,之后在把每一位转换成十进制相加,总和就是单独的那个数。

 1 int singleNumber(int* nums, int numsSize) {
 2     int ary[32] = {0};
 3     int res = 0;
 4     int i;
 5     int j;
 6     for(i = 0; i < 32; i++)
 7     {
 8         for(j = 0; j < numsSize; j++)
 9         {
10             ary[i] += ((nums[j] >> i) & 1);
11             ary[i] = ary[i] % 3;
12         }
13         res |= (ary[i] << i);
14     }
15     return res;
16 }

转:http://blog.csdn.net/feliciafay/article/details/19004479

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇260. Single Number III 下一篇28. Implement strStr()

评论

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

最新文章

热门文章

C 语言

C++基础

windows编程基础

linux编程基础

C/C++面试题目