首页 > 其他 > 详细

Single Number II

时间:2016-04-02 09:30:30      阅读:239      评论:0      收藏:0      [点我收藏+]

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?

这道题可以把所有的数看成是的位表示形式, 那么对于哪些出现了三次的数字,如果他们的那些数字如果第i bit位为1,那么我们加3次,再模除三,那么第i位就成为0; 如果第i bit 位位0,那么我们加3次,再模除三,那么第i位也会成为0。 第i位唯一不为1的就是多出来的那个数。

所以我们的做法就是把所有的数字按照bit位,每一位加起来模除3,然后最后剩下的就是我们要找的数,然后再把它按照每一位复原成为十进制的数。

 1 public class Solution {
 2     public int singleNumber(int[] nums) {
 3         if (nums == null || nums.length == 0) {
 4             return -1;
 5         }
 6         int result=0;
 7         int[] bits=new int[32];
 8         for (int i = 0; i < 32; i++) {
 9             for(int j = 0; j < nums.length; j++) {
10                 bits[i] += nums[j] >> i & 1;
11                 bits[i] %= 3;
12             }
13 
14             result |= (bits[i] << i);
15         }
16         return result;
17     }
18 }

 

Single Number II

原文:http://www.cnblogs.com/FLAGyuri/p/5346917.html

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