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

悠悠 2023-08-17 15:47 122阅读 0赞

## 题目 ##

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

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

## 思路 ##

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

b = (b ^ x) & ~a;
    a = (a ^ x) & ~b;

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

int len = nums.size();
    for(int i =0;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\]

## 代码 ##

1 class Solution {
     2 public:
     3 int singleNumber(vector<int>& nums) {
     4     int a = 0, b = 0;
     5     for (auto x : nums) {
     6         a = (a ^ x) & ~b;
     7         b = (b ^ x) & ~a;
     8     }
     9     return a;
    10 }
    11 };
    12 
    13 static const auto __lamda = []() {
    14     std::ios::sync_with_stdio(false);
    15     std::cin.tie(nullptr);
    16     return nullptr;
    17 }();

参考链接：[https://leetcode-cn.com/problems/single-number-ii/comments/][https_leetcode-cn.com_problems_single-number-ii_comments]

转载于:https://www.cnblogs.com/lfri/p/10349846.html

[https_leetcode-cn.com_problems_single-number-ii_comments]: https://leetcode-cn.com/problems/single-number-ii/comments/