leetcode--Single Number II

时间：2014-02-26 19:26:02 阅读：436 评论：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?

Have you been asked this question in an interview?

/**We can use the bit operation to do this problem
*If you have a problem to understand the bit operation,
*then you can think | , & , ^, ~ as the set operation union, intersection and symmetric difference and set complement respectively.
*/
 
public class Solution {
    public 
int singleNumber(int[] A) {
        int 
once = 0;
        int 
twice = 0;
        int 
triple = 0;
        for(int 
i = 0 ; i < A.length ; i++){
            //update twice when A[i] is added. if A[i] is in once, then added it to twice,
            //otherwise, twice is not needed to updated     
            twice |= A[i] & once;
           //update once
            once = A[i] ^ once;
           //triple is exactly the intersection of once and twice
            triple = once&twice;
           //update once and twice again(remove all integer in triple) 
            once ^= triple;
            twice ^= triple;
        }
        //return the integer in once or twice
        return 
once | twice;
    }
}        

leetcode--Single Number II

原文：http://www.cnblogs.com/averillzheng/p/3568218.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)