【leetcode刷题笔记】Single Number II

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?

题解：线性时间，O(1)的空间复杂度，只能把整数写成二进制的形式运算了。具体做法如下：

比如有一个数组｛5，5，5，3，2，3，3｝，这些数写成二进制如下：

5：101

3：011

2：010

3：011

我们分别统计这三位的1的个数，然后对3取模，得到每一位的结果结合起来就是010，就是只出现一次的数字2.

所以，我们可以设置一个32位的数组，然后对A中的所有数字，统计这32位中每一位上1的个数，然后对3取模，最后得到的32位的二进制数就是只出现一次的那个数了。

Java代码如下:

 public class Solution {

     public int singleNumber(int[] A) {

         int[] digits = new int[32];

         for(int i = 0;i < 32;i++){

             for(int j = 0;j < A.length;j++){

                 digits[i] += (A[j] >> i)&1;

             }

         }

         int result = 0;

         for(int i = 0;i < 32;i++){

             result += (digits[i]%3) << i;

         }

         return result;

     }

 }

巴特西

【leetcode刷题笔记】Single Number II

最新文章

热门文章