LeetCode-Single Number II

文章目录

LeetCode地址：https://leetcode.com/problems/single-number-ii/

Problem:
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?

思路

• 将数组A中每个整形的二进制 分散到一个32位数组A上求和，出现3次的在该位上的和肯定是3的倍数

public class Solution {
    public int singleNumber(int[] A) {
        int ret=0,index=0;
        int[] binarySum=new int[32];
        if(A==null || A.length==0)
            return ret;
        
        for(int i=0;i<A.length;i++)
        {
            index=0;
            do
            {
                binarySum[index++]+=A[i]%2;
                A[i]/=2;
            }while(A[i]!=0);
        }
        
        
        for(int i=0;i<binarySum.length;i++)
        {
            index=binarySum[i]%3;
            if(Math.abs(index)>1)
            {
                index=(index+3)%3;
            }
            ret+=Math.pow(2, i)*(index);
        }
        
        return ret;
    }
}

---

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。