Single Number II

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge

One-pass, constant extra space.

 

统计每一位上的1出现的次数，然后模3 ， 题目上的3 * n + 1给了提示，然后又做过一题2 * n + 1的位操作。

1 public class Solution { 2     /** 3      * @param A : An integer array 4      * @return : An integer  5      */ 6     public int singleNumberII(int[] A) { 7         int[] bit = new int[32]; 8          9         for(int a :A) {10             for(int i = 0;i<32;i++) {11                 if(((1 << i) & a) != 0) {12                     bit[i] = (bit[i] + 1) % 3;13                 }14             }15         }16         int res = 0;17         for(int i=31;i>=0;i--) {18             res = res * 2 + bit[i];19         }20         return res;21     }22 }