美文网首页
137. Single Number II

137. Single Number II

作者: juexin | 来源:发表于2017-01-09 18:31 被阅读0次

    Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
    Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

    class Solution {
    public:
        int singleNumber(vector<int>& nums) {
            int w = sizeof(int)*8;  //一个整数的字长
            int *count = new int[w];
            memset(count,0,sizeof(int)*w); //数组一定要初始化,否则会出现意外的值
            int n = nums.size();
            for(int i=0;i<w;i++)
              {
                  for(int j=0;j<n;j++)
                  {
                     count[i] += (nums[j]>>i)&0x01;
                  }
                  count[i] = count[i]%3;
              }
            int result=0;
            for(int i=0;i<w;i++)
            {
                result += (count[i]<<i);
            }
            return result;
        }
    };
    

    相关文章

      网友评论

          本文标题:137. Single Number II

          本文链接:https://www.haomeiwen.com/subject/iluhbttx.html