LeetCode137只出现一次的数字——位运算

题目

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现三次。找出那个只出现一次的元素。

说明：你的算法应该具有线性时间的复杂度。你可以不使用额外的空间来实现吗？

思路

题目要求线性复杂度，一般的算法做不到，不难想到用位运算。但怎么进行位运算，比较难想到。

b = (b ^ x) & ~a;

a = (a ^ x) & ~b;

^ 相当于除去原有元素，添加新元素， a &~  b 相当于从a集合中除去b集合中的所有元素。

int len = nums.size();

for(int i =;i < len;++i)
{

   b = (b ^ nums[i]) & ~a;

   a = (a ^ nums[i]) & ~b;
}

出现一次的存在b中，第二次出现从b中清除同时会存在a中，第三次出现会从b中清除。最终出现一次的都存在b中，出现两次的都存在a中。

例如：[1,2,2,1,1,2,99]

b={0}	{1}	{1，2}	{1}	{0}	{0}	{0}	{99}
a={0}	{0}	{0}	{2}	{1，2}	{2	{0}	{0}

代码

 class Solution {

 public:

 int singleNumber(vector<int>& nums) {

     int a = , b = ;

     for (auto x : nums) {

         a = (a ^ x) & ~b;

         b = (b ^ x) & ~a;

     }

     return a;

 }

 };

 static const auto __lamda = []() {

     std::ios::sync_with_stdio(false);

     std::cin.tie(nullptr);

     return nullptr;

 }();

续：

朋友面试竟然遇到了，前面的算法很讲究技巧性，不通用，补充一个较通用的方法：

int数组，32位，用一个32位的int数组，每一位记录值在该位出现1的次数。

其余元素出现3次，最后加起来肯定 %3 = 0。剩下的就是只出现一次的。

int bits[];

int singleNumber(vector<int>& nums)

{

    int res = ;

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

    {

        for(int j = ;j < nums.size();j++)

        {

            bits[i] += (nums[j]&);

            nums[j] >>= ;

        }

    }

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

        if(bits[i] % ) res += ( << i);

    return res;

}

参考链接：

1. https://leetcode-cn.com/problems/single-number-ii/comments/

2. https://www.cnblogs.com/fanguangdexiaoyuer/p/11585950.html

LeetCode137只出现一次的数字——位运算的相关教程结束。