首页 > 其他 > 详细

[LeetCode]Single Number II

时间:2014-02-18 10:24:52      阅读:240      评论: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?

思路

之前在Quora上看到一个用两个变量ones和twos分别统计1和2出现的次数来模拟“三进制”的方法。这次在网上又看到另一种解法也很不错,用一个长度为32的数组来统计每个位上1出现的次数,次数总和为3的倍数表明我们要求的数在该位是0,否则为1.

 

代码

bubuko.com,布布扣
public int singleNumber2(int[] A)
     {
         /* 注释内为用ones和twos统计1和2出现次数的解法
int ones=0,twos=0;
int n=A.length; //int result=A[0]; for(int i=0;i<n;i++) { int tmp=ones; ones=(tmp^A[i])&(~twos); twos=(tmp&A[i])|(twos&(~A[i])); } return ones; */ int[] count=new int[32]; for(int i=0;i<A.length;i++) { int num=A[i]; for(int j=0;j<32;j++) { if((num&(1<<j))!=0) count[j]++; } } int ans=0; for(int i=0;i<32;i++) { if(count[i]%3!=0) ans+=1<<i; } return ans; }
bubuko.com,布布扣

[LeetCode]Single Number II

原文:http://www.cnblogs.com/developerY/p/SingleNumber2.html

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