[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?

题意：给定数组，除一个数仅出现一次外，其余都出现三次，找到仅出现一次的数字。

思路：这题不能延续single number的解法，但是思路可以向逻辑运算符那边靠。这题我开始没有想出来，这个逻辑运算对我而言是一个大坑。看了Grandyang的博客才明白。这里给出原博客中的解释：用3个整数来表示INT的各位的出现次数情况，one表示出现了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值，

ones 代表第ith 位只出现一次的掩码变量；twos 代表第ith 位只出现两次的掩码变量；threes 代表第ith 位只出现三次的掩码变量。

博主的个人理解经验是：写出一个例子，按照程序走一遍。

 class Solution {

 public:

     int singleNumber(int A[], int n)

     {

         int one=,two=,three=;

         for(int i=;i<n;++i)

         {

             two |=one&A[i];

             one ^=A[i];

             three=one&two;

             one &=~three;

             two &=~three;

         }

         return one;

     }

 };

原博客中还给出了Single Number III

巴特西

[Leetcode] single number ii 找单个数

最新文章

热门文章