LeetCode:Single Number II

题目:

Given an array of integers, every element appearsthree 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

解题思路:

思路类似基数排序，将所有数字列成n行，然后观察其中的一列，你会发现，由于其他数字都出现了

三次，如果当前这列某个数位的个数不能被3整除，那么，所要求的数在此位必等于这个数位的值，这样

就能以O(n)的时间复杂度解决问题了(注:此处常系数是10).

下面是解题代码.

class Solution {
public:
    int singleNumber(int A[], int n) 
    {
        int div[10] = {1} , cnt = 0 , res = 0;
        for(int i=1;i<10;++i)
            div[i] = div[i-1] * 10 ;
        for(int i=0;i
  
   

注:abs((long long)A[j])中要将A[j]强制转换为long long型，不然程序有bug，比如A[j]等于-2^31.