[leetcode260][位运算]只出现一次的数字 Ⅲ

发布于 2021-10-30  612 次阅读


https://leetcode-cn.com/problems/single-number-iii/

有两个数字只出现了一次 其余数字都是出现了两次

思路 相同数字异或为0 所有数字异或结果必不为0

异或结果取最后一位1 说明两个数在这一位不相同(这一步思路很巧妙 t&(-t)-t是t取反后加1 正好可以取得最后一位1

用上一步取得的1去进行&运算 这一位是1的 放到一边 这一位是0的放到一边 这两个数必定一个在一遍 得到答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
      ll t=0;//用来异或
      for(ll i:nums){
        t^=i;
      }
      ll last1=t&(-t);//获得最后一位1
      vector<int> ans(2,0);
      for(int i:nums){
        if(i&(last1)){
          ans[0]^=i;
        }
        else{
          ans[1]^=i;
        }
      }
      return ans;
    }
};

愿风指引你的道路,愿你的刀刃永远锋利。